在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 有八位来表示输入的签名 bit-string:

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

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

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

要了解 CRC-8 电路的操作，请查看在线提供的动画 CRC calculators 之一。您还可以查看 CRC computation.

上的维基百科文章

使用 C# 程序（见下文），我做了这个实验。无论输入 bit-string（from-left-to-right 或相反）的顺序如何，65536 个 bit-string 中的 256 个具有相同的签名。对于仅提供 256 种不同签名的 8 位散列方法，我们还能期待什么？

我的代码：

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}");
        }
    }
}

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

Get all possible combinations of bit flips in Matlab for CRC calculation

matlab

combinations

bit

combinatorics

crc