El Checksum es un método de detección de errores que detecta errores en los datos/mensajes mientras se transmite del remitente al receptor. Este método es utilizado por los protocolos de capa superior y utiliza el generador de suma de comprobación en el lado del remitente y el verificador de suma de comprobación en el lado del receptor.
Ejemplos:
Entrada: mensaje_enviado = «10101111», mensaje_recepción = «10101101», tamaño_bloque = 8
Salida: Explicación del error
: dado que el séptimo bit en el mensaje_enviado y el mensaje_recepción es diferente, el valor final de la suma de comprobación no es igual a cero, lo que indica que se ha producido algún error durante la transmisión.Entrada: mensaje_enviado = «10000101011000111001010011101101», mensaje_rec = «10000101011000111001010011101101», tamaño_bloque = 8
Salida: Sin error
Enfoque: El problema dado se puede dividir en dos partes siguientes:
- La generación del valor de suma de comprobación del mensaje del remitente se puede realizar mediante los siguientes pasos:
- Divida el mensaje en las strings binarias del tamaño de bloque dado .
- Todas las strings binarias se suman para obtener la suma .
- El complemento a uno de la string binaria que representa la suma es el valor de suma de comprobación requerido.
- Compruebe si el valor del mensaje recibido (es decir, rec_message + senders_checksum ) es igual a 0 .
- La suma de verificación del mensaje recibido se puede calcular de manera similar a la suma de verificación calculada en el proceso anterior.
- Si el valor de la suma de comprobación es 0 , el mensaje se transmite correctamente sin errores; de lo contrario, se ha producido algún error durante la transmisión.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find the One's complement
// of the given binary string
string Ones_complement(string data)
{
for (int i = 0; i < data.length(); i++) {
if (data[i] == '0')
data[i] = '1';
else
data[i] = '0';
}
return data;
}
// Function to return the checksum value of
// the give string when divided in K size blocks
string checkSum(string data, int block_size)
{
// Check data size is divisible by block_size
// Otherwise add '0' front of the data
int n = data.length();
if (n % block_size != 0) {
int pad_size = block_size - (n % block_size);
for (int i = 0; i < pad_size; i++) {
data = '0' + data;
}
}
// Binary addition of all blocks with carry
string result = "";
// First block of data stored in result variable
for (int i = 0; i < block_size; i++) {
result += data[i];
}
// Loop to calculate the block
// wise addition of data
for (int i = block_size; i < n; i += block_size) {
// Stores the data of the next bloack
string next_block = "";
for (int j = i; j < i + block_size; j++) {
next_block += data[j];
}
// Stores the binary addition of two blocks
string additions = "";
int sum = 0, carry = 0;
// Loop to calculate the binary addition of
// the current two blocls of k size
for (int k = block_size - 1; k >= 0; k--) {
sum += (next_block[k] - '0')
+ (result[k] - '0');
carry = sum / 2;
if (sum == 0) {
additions = '0' + additions;
sum = carry;
}
else if (sum == 1) {
additions = '1' + additions;
sum = carry;
}
else if (sum == 2) {
additions = '0' + additions;
sum = carry;
}
else {
additions = '1' + additions;
sum = carry;
}
}
// After binary add of two blocks with carry,
// if carry is 1 then apply binary addition
string final = "";
if (carry == 1) {
for (int l = additions.length() - 1; l >= 0;
l--) {
if (carry == 0) {
final = additions[l] + final;
}
else if (((additions[l] - '0') + carry) % 2
== 0) {
final = "0" + final;
carry = 1;
}
else {
final = "1" + final;
carry = 0;
}
}
result = final;
}
else {
result = additions;
}
}
// Return One's complements of result value
// which represents the required checksum value
return Ones_complement(result);
}
// Function to check if the received message
// is same as the senders message
bool checker(string sent_message,
string rec_message,
int block_size)
{
// Checksum Value of the senders message
string sender_checksum
= checkSum(sent_message, block_size);
// Checksum value for the receivers message
string receiver_checksum = checkSum(
rec_message + sender_checksum, block_size);
// If receivers checksum value is 0
if (count(receiver_checksum.begin(),
receiver_checksum.end(), '0')
== block_size) {
return true;
}
else {
return false;
}
}
// Driver Code
int main()
{
string sent_message
= "10000101011000111001010011101101";
string recv_message
= "10000101011000111001010011101101";
int block_size = 8;
if (checker(sent_message,
recv_message,
block_size)) {
cout << "No Error";
}
else {
cout << "Error";
}
return 0;
}
No Error
Complejidad de tiempo: O(N)
Espacio auxiliar: O(block_size)
Publicación traducida automáticamente
Artículo escrito por raselmeya2194 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA