通过二进制字符串和多项式字符串计算CRC [英] Calculate CRC by Binary String and Polynomial String

问题描述

尝试在程序中实现CRC计算器时遇到一些问题。

我有2个输入：

1）二进制字符串（消息）。 />
2）第二个二进制字符串（多项式）。

程序必须计算crc，计算消息和多项式之间除数的余数。

例如：

输入数据是11000010.

作为生成多项式（=除数），让我们使用100011101.

除数有9位（因此这是一个CRC-8多项式），所以在输入模式上附加8个零位。

将除数的前导'1'与divident的第一个'1'对齐并执行一步逐步学校分工，每个位使用XOR操作：

 1100001000000000 
 100011101 
 -------- -  
 010011001 
 100011101 
 ---------- 
 000101111 
 100011101（*）
 -------- -  
 001100101 
 100011101 
 --------- 
 010001001 
 100011101 
 --------- 
 000001111< ------最终产出

有人能帮帮我吗？谢谢！



[更新]

<前lang =c＃> public 静态 字符串 BinDivRemainder（ string dividendo， string divisore）
{
dividendo.TrimStart（' 0' ）;
divisore.TrimStart（' 0'）;
int pos1 = 0 ;
string xor = ;
执行
{
for （ int i = pos1; i < divisore.Length; i ++）
{
if （dividendo [i] == divisore [i]）xor + = ' 0' ;
else xor + = ' 1'< /跨度>;
}
pos1 = GetFirst1Pos（xor）;

if （pos1 < 0 ） return xor;
divisore = xor;
} while （ true ）;

return xor;
}
私有 静态 int GetFirst1Pos（ string bin）
{
for （ int i = 0 ; i < bin。长度; i ++）
{
如果（bin [i] == ' 1'） return i;
}
return -1;
}

但是功课说明输入数据必须是从12到20个字符和多项式最多4个字符（我不知道这些信息是否有用于构建算法）

请帮助我谢谢...

解决方案

你的代码没有你想象的那样，你不明白为什么！



几乎是通用的解决方案：逐步在调试器上运行代码，检查变量。

掌握Visual Studio 2010中的调试 - 初学者指南 [ ^ ]



此解决方案的缺点：

- 这是一个DIY，你是追踪问题并找到根源的人，导致解决方案。

这个解决方案的好处：

- 你看到你的代码行为，你把它与你的期望相匹配。



次要效果

- 你会为自己找到虫子感到骄傲。

- 你的技能会提高。



你应该很快就会发现什么是错的。



建议：

- 你可以运行调试器你的代码只是为了看错了，它总是很有趣。

- 你的代码每个字符编码1位。但你也说

引用：

1）二进制字符串（消息）。

2）第二个二进制字符串（多项式）。

这通常意味着char编码8位，这是矛盾的，你必须澄清什么是什么。我担心你必须抛弃你所有的代码。

- Xor操作从未与除法或余数有关。您正在计算CRC。

I have some problems trying to implement a CRC calculator in a program.
I have 2 Inputs:
1) A binary string (the message).
2) A second binary string (the polynomial).
The program must calculate the crc calculating the remainder from the division between message and polynomial.
For example:
Input data is 11000010.
As generator polynomial (=divisor), let's use 100011101.
The divisor has 9 bits (therefore this is a CRC-8 polynomial), so append 8 zero bits to the input pattern .
Align the leading '1' of the divisor with the first '1' of the divident and perform a step-by-step school-like division, using XOR operation for each bit:

1100001000000000
100011101
---------
010011001
 100011101
 ----------
 000101111
    100011101           (*)
    ---------
    001100101
      100011101
      ---------
      010001001
       100011101
       ---------
       000001111 <------ THE FINAL OUTPUT

Can someone help me? Thank you!

[Update]

public static string BinDivRemainder(string dividendo,string divisore)
       {
           dividendo.TrimStart('0');
           divisore.TrimStart('0');
           int pos1 = 0;
           string xor = "";
           do
           {
               for (int i = pos1; i < divisore.Length; i++)
               {
                   if (dividendo[i] == divisore[i]) xor += '0';
                   else xor += '1';
               }
               pos1 = GetFirst1Pos(xor);

               if (pos1 < 0) return xor;
               divisore = xor;
           } while (true);

           return xor;
       }
       private static int GetFirst1Pos(string bin)
       {
           for (int i = 0; i < bin.Length; i++)
           {
               if (bin[i] == '1') return i;
           }
           return -1;
       }

However the homework tell that the input data must be from 12 to 20 characters and the polynomial maximum 4 characters (I don't know if these informations are usefull to build the algorithm)
Please help me thank you...

解决方案

Your code do not behave the way you expect, and you don't understand why !

There is an almost universal solution: Run your code on debugger step by step, inspect variables.
Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]

The downside of this solution:
- It is a DIY, you are the one tracking the problem and finding its roots, which lead to the solution.
The upside of this solution:
- You see your code behaviour, you match it against your expectations.

secondary effects
- Your will be proud of finding bugs yourself.
- Your skills will improve.

You should find pretty quickly what is wrong.

Advices:
- You can run the debugger on your code just to see what is wrong, it is always interesting.
- Your code is encoding 1 bit per char. but you also say

Quote:

1) A binary string (the message).
2) A second binary string (the polynomial).

Which usually mean that a char is encoding 8 bits, this is contradictory, you must clarify what is what. I fear you have to throw away all your code.
- Xor operation have never been related to division or remainder. You are computing a CRC.

这篇关于通过二进制字符串和多项式字符串计算CRC的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！