CRC简单计算

背景

CRC,即循环冗余校验(Cyclic redundancy check),是一种依原始数据产生简短固定位数校验码的方法,由W. Wesley Peterson于1961年发表。

CRC主要用来检测或校验数据传输或者保存后是否出现错误,它虽然不能纠错,但是其生成的检验码的方法简单,容易使用硬件实现,且善于检测传输通道干扰引起的错误,所以得到了广泛应用。

CRC校验的正确率与多项式有一定关系。当且仅当误码能够被CRC多项式整除时,CRC算法无法检查到错误。一般而言,如果数据中有个别位出现错误,CRC都可以检测出来。

Python计算冗余码

来自Wikipedia的示例程序,为其添加了相关注释,如下:

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

def crc_remainder(input_bitstring, polynomial_bitstring, initial_filler):
    '''
    Calculates the CRC remainder of a string of bits using a chosen polynomial.

    Parameters
    ----------
    input_bitstring : string

    polynomial_bitstring: string

    initial_filler: string(char)
        '1' or '0'

    Returns
    -------
    crc_code : string
        The initial CRC remainder for a chosen input and polynomial, with either 1 or 0 as the initial padding.

    Examples
    --------
    >>> crc_remainder('10111001', '1101', '1')
    '010'
    >>> crc_remainder('10111001', '1101', '0')
    '101'

    Notes
    -----
    This code is excerpted from Wikipedia: https://en.wikipedia.org/wiki/Cyclic_redundancy_check
    '''
    len_input = len(input_bitstring)

    polynomial_bitstring = polynomial_bitstring.lstrip('0')
    initial_padding = initial_filler * (len(polynomial_bitstring) - 1)
    input_padded_array = list(input_bitstring + initial_padding)

    while '1' in input_padded_array[:len_input]:
        cur_shift = input_padded_array.index('1')
        for i in range(len(polynomial_bitstring)):
            input_padded_array[cur_shift + i] = str(
                int(input_padded_array[cur_shift + i]) ^ int(polynomial_bitstring[i]))

        # print(input_padded_array)

    return ''.join(input_padded_array)[len_input:]

基本计算方法,就是原数据码循环异或生成多项式,待原数据全0时,得到的码即为CRC检验码。

结束语

生成多项式的选择是CRC算法实现中最重要的部分,设计CRC生成多项式的一个通用数学原则是,使多项式满足所有模运算不可分解多项式的约束条件(多项式除了1与它自身之外不能被任何其它的多项式整除)。CRC更多相关内容可以参考Wikipedia或类似资源。

参考:

  1. Wikipedia.org – Cyclic redundancy check

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google photo

You are commenting using your Google account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s