循环冗余校验和Modulo-2分区

2021年5月3日17:01:54 发表评论 1,014 次浏览

本文概述

Python3
C ++

CRC或循环冗余校验是一种检测通信信道中意外更改/错误的方法。

CRC使用生成多项式在发送方和接收方均可用。示例生成器多项式的形式如x3+ x +1。此生成多项式表示键1011。另一个示例是x2+1代表键101。

n : Number of bits in data to be sent 
    from sender side.  
k : Number of bits in the key obtained 
    from generator polynomial.

发送方(从数据和生成多项式(或密钥)生成编码数据)：

首先通过在数据末尾添加k-1个零来扩充二进制数据

使用modulo-2二进制除法可通过键对二进制数据进行除法并存储除法的余数。

在数据末尾追加其余部分以形成编码数据并发送

接收方(检查传输中是否引入了错误)

再次执行模2除法, 如果余数为0, 则没有错误。

在本文中, 我们将只专注于查找余数, 即校验字和代码字。

模2部门：

模2二进制除法的过程与我们用于十进制数的常见除法过程相同。只是, 我们在这里使用XOR而不是减法。

在每个步骤中, 将除数(或数据)的副本与被除数(或键)的k位进行异或。
XOR操作的结果(余数)为(n-1)位, 将其拉低1位以使其为n位长后, 将用于下一步。
当没有剩余可下拉的位时, 我们得到结果。 (n-1)位余数附加在发送方。

插图：

示例1(传输无错误)：

Data word to be sent - 100100
Key - 1101 [ Or generator polynomial x3 + x2 + 1]

Sender Side:

Therefore, the remainder is 001 and hence the encoded 
data sent is 100100001.

Receiver Side:
Code word received at the receiver side  100100001

Therefore, the remainder is all zeros. Hence, the
data received has no error.

示例2 ：(传输错误)

Data word to be sent - 100100
Key - 1101

Sender Side:

Therefore, the remainder is 001 and hence the 
code word sent is 100100001.

Receiver Side
Let there be an error in transmission media
Code word received at the receiver side - 100000001
 

Since the remainder is not all zeroes, the error
is detected at the receiver side.

实现

以下是从给定的二进制数据和密钥生成代码字的Python实现。

# Returns XOR of 'a' and 'b'
# (both of same length)
def xor(a, b):
  
     # initialize result
     result = []
  
     # Traverse all bits, if bits are
     # same, then XOR is 0, else 1
     for i in range ( 1 , len (b)):
         if a[i] = = b[i]:
             result.append( '0' )
         else :
             result.append( '1' )
  
     return ''.join(result)
  
  
# Performs Modulo-2 division
def mod2div(divident, divisor):
  
     # Number of bits to be XORed at a time.
     pick = len (divisor)
  
     # Slicing the divident to appropriate
     # length for particular step
     tmp = divident[ 0 : pick]
  
     while pick <len (divident):
  
         if tmp[ 0 ] = = '1' :
  
             # replace the divident by the result
             # of XOR and pull 1 bit down
             tmp = xor(divisor, tmp) + divident[pick]
  
         else :   # If leftmost bit is '0'
             # If the leftmost bit of the dividend (or the
             # part used in each step) is 0, the step cannot
             # use the regular divisor; we need to use an
             # all-0s divisor.
             tmp = xor( '0' * pick, tmp) + divident[pick]
  
         # increment pick to move further
         pick + = 1
  
     # For the last n bits, we have to carry it out
     # normally as increased value of pick will cause
     # Index Out of Bounds.
     if tmp[ 0 ] = = '1' :
         tmp = xor(divisor, tmp)
     else :
         tmp = xor( '0' * pick, tmp)
  
     checkword = tmp
     return checkword
  
# Function used at the sender side to encode
# data by appending remainder of modular division
# at the end of data.
def encodeData(data, key):
  
     l_key = len (key)
  
     # Appends n-1 zeroes at end of data
     appended_data = data + '0' * (l_key - 1 )
     remainder = mod2div(appended_data, key)
  
     # Append remainder in the original data
     codeword = data + remainder
     print ( "Remainder : " , remainder)
     print ( "Encoded Data (Data + Remainder) : " , codeword)
  
# Driver code
data = "100100"
key = "1101"
encodeData(data, key)

输出如下：

('Remainder : ', '001')
('Encoded Data (Data + Remainder) : ', '100100001')

输出如下：

Remainder :  001
Encoded Data (Data + Remainder) :  100100001

请注意, CRC主要设计用于防止通信信道上常见的错误, 而不适用于防止数据有意更改(请参阅原因)。这里)

使用位操作的实现：

CRC码字的生成也可以使用以下位处理方法来完成：

Python3

# Python program to generate CRC codeword
from math import log, ceil
  
def CRC(dataword, generator):
     dword = int (dataword, 2 )
     l_gen = len (generator)
  
     # append 0s to dividend
     dividend = dword <<(l_gen - 1 )    
  
     # shft specifies the no. of least significant
     # bits not being XORed
     shft = ceil(log(dividend + 1 , 2 )) - l_gen     
  
     # ceil(log(dividend+1 , 2)) is the no. of binary 
     # digits in dividend
     generator = int (generator, 2 )
  
     while dividend> = generator or shft> = 0 :
  
         # bitwise XOR the MSBs of dividend with generator
         # replace the operated MSBs from the dividend with 
         # remainder generated
         rem = (dividend>> shft) ^ generator    
         dividend = (dividend & (( 1 <<shft) - 1 )) | (rem <<shft)
          
         # change shft variable
         shft = ceil(log(dividend + 1 , 2 )) - l_gen
  
     # finally, AND the initial dividend with the remainder (=dividend)
     codeword = dword <<(l_gen - 1 )|dividend
     print ( "Remainder:" , bin (dividend).lstrip( "-0b" ))
     print ( "Codeword :" , bin (codeword).lstrip( "-0b" ))
  
# Driver code
dataword = "10011101"
generator = "1001"
CRC(dataword, generator)

C ++

//C++ Program to generate CRC codeword
#include<stdio.h>
#include<iostream>
#include<math.h>
  
using namespace std;
  
//function to convert integer to binary string
string toBin( long long int num){
     string bin = "" ;
     while (num){
         if (num & 1)
             bin = "1" + bin;
         else
             bin = "0" + bin;
         num = num>>1;
     }
     return bin;
}
  
//function to convert binary string to decimal
long long int toDec(string bin){
     long long int num = 0;
     for ( int i=0; i<bin.length(); i++){
         if (bin.at(i)== '1' )
             num += 1 <<(bin.length() - i - 1);
     }
     return num;
}
  
//function to compute CRC and codeword
void CRC(string dataword, string generator){
     int l_gen = generator.length();
     long long int gen = toDec(generator);
  
     long long int dword = toDec(dataword);
  
      //append 0s to dividend
     long long int dividend = dword <<(l_gen-1);       
  
     //shft specifies the no. of least 
     //significant bits not being XORed
     int shft = ( int ) ceill(log2l(dividend+1)) - l_gen;  
     long long int rem;
  
     while ((dividend>= gen) || (shft>= 0)){
  
         //bitwise XOR the MSBs of dividend with generator
         //replace the operated MSBs from the dividend with
         //remainder generated 
         rem = (dividend>> shft) ^ gen;                
         dividend = (dividend & ((1 <<shft) - 1)) | (rem <<shft);
  
         //change shft variable
         shft = ( int ) ceill(log2l(dividend + 1)) - l_gen;
     }
  
     //finally, AND the initial dividend with the remainder (=dividend)
     long long int codeword = (dword <<(l_gen - 1)) | dividend;
     cout <<"Remainder: " <<toBin(dividend) <<endl;
     cout <<"Codeword : " <<toBin(codeword) <<endl;
}
  
int main(){
     string dataword, generator;
     dataword = "10011101" ;
     generator = "1001" ;
     CRC(dataword, generator);
     return 0;
}

输出如下：