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

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

## 本文概述

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位进行异或。
• XOR操作的结果(余数)为(n-1)位, 将其拉低1位以使其为n位长后, 将用于下一步。
• 当没有剩余可下拉的位时, 我们得到结果。 (n-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.

Therefore, the remainder is all zeros. Hence, the

``````Data word to be sent - 100100
Key - 1101

Sender Side:

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

Let there be an error in transmission media

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

``````# 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码字的生成也可以使用以下位处理方法来完成：

## 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;
}``````

``````Remainder: 100
Codeword : 10011101100``````

https://en.wikipedia.org/wiki/Cyclic_redundancy_check