在Matlab中获取所有可能的位翻转组合以进行CRC计算。

Question

我正在Matlab中做一些CRC测试。我有一个CRC-8功能，我想知道哪个组合的位翻转导致完全相同的CRC。

让我们考虑一下这样的位数组

Input = [1,1,0,1,0,0,0,0,1,0,1,0,0,0,0,1];

现在，我将如何处理每一个可能的位翻转组合？我做了一些研究，但没有找到一个好的答案，也许你能帮上忙。

Answer 1

CRC-8有八个位来表示输入位字符串的签名：

​

​

您的实验可以是生成所有可能的2^n，长度为n的不同输入位字符串，并注册导致给定签名的所有字符串。

请注意，对于每个实验，您必须从相同的初始8位状态字开始。

您的示例输入是16位长。有2^16 = 65536不同的位串可能与16位.尝试它们中的每一个，找出哪些字符串导致与输入相同的签名。

要了解CRC-8电路的操作，请查看在线可用的动画CRC calculators之一。你也可以看看维基百科在CRC计算上的文章。

使用C#程序(见下文)，我做了这个实验。不管输入位字符串的顺序(从左到右，反之亦然)，65536位字符串中的256个具有相同的签名。我们还能从8位散列方法中得到更多的期望，它只提供了256个不同的签名？

我的代码：

using System;

namespace akCrc8Eval
{
    class Crc8Evaluator
    {
        // CRC 8 lookup table
        // https://github.com/WasatchPhotonics/CRC8_Example
        private static byte[] CRC_8_TABLE =
            {
              0, 94,188,226, 97, 63,221,131,194,156,126, 32,163,253, 31, 65,
            157,195, 33,127,252,162, 64, 30, 95,  1,227,189, 62, 96,130,220,
             35,125,159,193, 66, 28,254,160,225,191, 93,  3,128,222, 60, 98,
            190,224,  2, 92,223,129, 99, 61,124, 34,192,158, 29, 67,161,255,
             70, 24,250,164, 39,121,155,197,132,218, 56,102,229,187, 89,  7,
            219,133,103, 57,186,228,  6, 88, 25, 71,165,251,120, 38,196,154,
            101, 59,217,135,  4, 90,184,230,167,249, 27, 69,198,152,122, 36,
            248,166, 68, 26,153,199, 37,123, 58,100,134,216, 91,  5,231,185,
            140,210, 48,110,237,179, 81, 15, 78, 16,242,172, 47,113,147,205,
             17, 79,173,243,112, 46,204,146,211,141,111, 49,178,236, 14, 80,
            175,241, 19, 77,206,144,114, 44,109, 51,209,143, 12, 82,176,238,
             50,108,142,208, 83, 13,239,177,240,174, 76, 18,145,207, 45,115,
            202,148,118, 40,171,245, 23, 73,  8, 86,180,234,105, 55,213,139,
             87,  9,235,181, 54,104,138,212,149,203, 41,119,244,170, 72, 22,
            233,183, 85, 11,136,214, 52,106, 43,117,151,201, 74, 20,246,168,
            116, 42,200,150, 21, 75,169,247,182,232, 10, 84,215,137,107, 53
        };

        // Calculate 8-bit signature for byte array
        // inspired by:  https://github.com/WasatchPhotonics/CRC8_Example
        public byte Calc_CRC_8(byte[] DataArray, int Length)
        {
            byte CRC = 0;  //  initial value always 0

            for (int i = 0; i < Length; i++)
            {
                CRC = CRC_8_TABLE[CRC ^ DataArray[i]];
            }

            return CRC;
        }

        // Calculate 8-bit signature for 16-bit unsigned int
        private byte Calc_CRC_8(UInt16 n)
        {
            const int DIM = 16;
            byte CRC = 0;  //  initial value always 0

            for (int i = 0; i < DIM; i++)
            {
                byte b = (byte)(((n & (1 << i)) == 0) ? 0 : 1);
                CRC = CRC_8_TABLE[CRC ^ b];
            }

            return CRC;
        }

        public void getBitStringsWithSameSignature(byte[] bytes)
        {
            byte sig = Calc_CRC_8(bytes, bytes.Length);
            int count = 0;

            for (int n = 0; n < UInt16.MaxValue; n++)
            {
                if (sig == Calc_CRC_8((UInt16)n))
                {
                    count++;
                }
            }

            Console.WriteLine($"Found {count} bit-strings with signature {sig}");
        }
    }
}