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

本文概述

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 - 100100Key - 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 side100100001Therefore, the remainder is all zeros. Hence, thedata received has no error.

示例2 ：(传输错误)

Data word to be sent - 100100Key - 1101Sender Side:Therefore, the remainder is 001 and hence the code word sent is 100100001.Receiver SideLet there be an error in transmission mediaCode word received at the receiver side - 100000001 Since the remainder is not all zeroes, the erroris 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 = https://www.lsbin.com/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 = "https://www.lsbin.com/100100" key = "1101" encodeData(data, key)

输出如下：

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

输出如下：

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

请注意, CRC主要设计用于防止通信信道上常见的错误, 而不适用于防止数据有意更改(请参阅原因)。这里)
使用位操作的实现：
CRC码字的生成也可以使用以下位处理方法来完成：
Python3

# Python program to generate CRC codeword from math import log, ceildef 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; }

输出如下：

Remainder: 100Codeword : 10011101100

参考文献：
https://en.wikipedia.org/wiki/Cyclic_redundancy_check
本文作者：杰伊·帕特尔(Jay Patel)。如果你喜欢lsbin并希望做出贡献, 那么你也可以写一篇文章并将你的文章邮寄到contribution@lsbin.org。查看你的文章出现在lsbin主页上, 并帮助其他Geeks。
【循环冗余校验和Modulo-2分区】如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。