我正在尝试为我正在从事的一个项目实现位填充,即一个简单的软件 AFSK 调制解调器。简化的协议(protocol)看起来像这样:
0111 1110 # burst sequence
0111 1110 # 16 times 0b0111_1110
...
0111 1110
...
... # 80 bit header (CRC, frame counter, etc.)
...
0111 1110 # header delimiter
...
... # data
...
0111 1110 # end-of-frame sequence
现在我需要在接收到的数据中找到保留序列0111 1110
,因此必须确保 header 和数据都不包含六个连续的1
。这可以通过位填充来完成,例如在每个五个 1
的序列后插入一个零:
11111111
转换为
111110111
和
11111000
转换为
111110000
如果我想有效地实现这一点,我想我不应该使用 1
和 0
数组,我必须将数据字节转换为 1
和0
,然后填充一个数组等。但是静态大小的位域似乎也不适合,因为由于位填充,内容的长度是可变的。
我可以使用哪种数据结构来更有效地进行位填充?
最佳答案
我现在才看到这个问题,看到它没有答案并且没有删除,我会继续回答。它可能会帮助其他看到此问题并提供解决方案的人。
位填充:这里1的
的最大连续序列是5
。在 5
1's
之后,应该在 5
1's
之后附加一个 0
。
这是执行此操作的 C 程序:
#include <stdio.h>
typedef unsigned long long int ulli;
int main()
{
ulli buf = 0x0fffff01, // data to be stuffed
temp2= 1ull << ((sizeof(ulli)*8)-1), // mask to stuff data
temp3 = 0; // temporary
int count = 0; // continuous 1s indicator
while(temp2)
{
if((buf & temp2) && count <= 5) // enter the loop if the bit is `1` and if count <= 5
{
count++;
if(count == 5)
{
temp3 = buf & (~(temp2 - 1ull)); // make MS bits all 1s
temp3 <<= 1ull; // shift 1 bit to accomodeate the `0`
temp3 |= buf & ((temp2) - 1); // add back the LS bits or original producing stuffed data
buf = temp3;
count = 0; // reset count
printf("%llx\n",temp3); // debug only
}
}
else
{
count = 0; // this was what took 95% of my debug time. i had not put this else clause :-)
}
temp2 >>=1; // move on to next bit.
}
printf("ans = %llx",buf); // finally
}
这样做的问题是,如果连续 5 个 1 的数量超过 10 个,则可能会溢出。最好先进行划分,然后进行整理并重复。
关于encoding - 我应该使用哪种数据结构进行位填充?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11614152/