转网上一些问题的讨论，作为备份，以备以后学习之用-某wireless协议

bad_fpga

转自
http://www.socvista.com/bbs/viewthread.php?tid=549&extra=page%3D1&page=1

问题背景：某wireless协议。

问题描述：
发送方一次发送7个连续帧，这七个帧被分为若干个组，但是最多为5组。分组的情况用7比特信号i_group[6:0]来表示，第N个比特代表第N个帧的分组情况。当第N比特为0时表示与其相对应的第N帧是一个新组的开始，当第N比特为1时表示第N帧与前面的帧同属一组。比如7'b0101110就表示第0、1、2、3帧属于一组，第4、5帧属于一组，第6帧单独一组。
然后我们来计算一个以组为单位的group-ack-bitmap，这个信号叫o_grp_map[4:0]，因为最多5个组，所以这个信号也只有5比特。当第G组的所有帧都正确时，o_grp_map的第G比特才标记为1，否则第G比特标记为零。
关于7个帧的正确与否，由信号i_frm_map[6:0]给出，因为最多7个帧，所以这个信号也只有7比特。当第F帧正确时，o_frm_map的第F比特标记为1，否则标记为零。

解题要求：在已经收到 i_group[6:0]和i_frm_map[6:0]的条件下，计算出o_grp_map[4:0]
请说明思路，最好用HDl语言描述。需要几个时钟？能否在1个时钟内完成？

=======================================================================================================================================
以下内容为原贴的一些精彩回复
dancia ：
这个题仔细想了想，其实没有看起来那么复杂。根据题意，输入i_group为7bit，再根据最开始应当是第一组的开始，所以最高位肯定为0，再根据分组不超过5组，去掉7bit中多于5个0的情况，实际剩下57种可能性。使用查表的方法就能搞定，应该速度也不慢。另外，case太多，不保证没有笔误，反正思路应该对的。。。
点击此处下载 ourdev_553064.rar(文件大小:736字节) (原文件名:ACK_v1.rar)

dancia ：
第二种解法，找出错误的帧对应的分组。将该组对应标志位置1，分组数不到5时，多余bit也置0.testbench稍后补上，感觉应该是对的。

根据kobe老大提醒：本代码对各个比特位置的定义和题目要求刚好搞反了，大家就看看思路吧，-_-。。。。。。
点击此处下载 ourdev_553065.rar(文件大小:581字节) (原文件名:ACK_v2.rar)

dancia ：
举例子说明吧，
1）查表的方法，这种方法的前提就是给定了输入的可能性，而且输入的可能性并不太多，所以我们可以事先用手或者别的方法算出答案。
比如i_group = 7'b0111011，这意味着什么呢？就意味着输入的所有帧被编为2组，第一组包括0，1，2，3帧，第二组包括4，5，6帧。对应的如果i_frm_map[6:3]都为1的话,第一组校验正确，o_grp_map[4]为1。i_frm_map[2:0]都正确的话，第二组校验正确，o_grp_map[3]为1。由于只有2组，o_grp_map[2:0]都置为0.同理，对其他输入的i_group，我们都能实现判断出分组情况，做成一张表就行了。
这种方法的好处在于，思维直接明了，输入输出一一对应。缺点是如果输入数据变了，比如变成8位或者9位了，整个表就得重来，编制表的过程会很麻烦，而且输入位数较多的时候，可能电路会很慢。

2）第二种方法的主要思想是，找出错误帧对应的分组。如何知道每一帧在哪个组呢？就把输入反一下，相加，比如i_group= 0010000,那个1明显对应第2组，n_i_group = 1101111，1+1+0 =2,就是第二组。这样如果i_frm_map[4]为0，就对应第二个分组错了。最后再分组进行一下判断，只要每组包含的所有帧都正确，那该组就正确。就解释这么多了，大家看看代码看看就清楚了。

james：
第二种方法的思路我再总结一下：
1. 逐帧判断对错。如果某帧有错，用数零的方法确定该帧来自第几组，dancia用zero_n表示，其实含义就是error_n_from。
2. 逐组判断对错。在判断第N组时，检查所有错误帧对应的组，只有全都不属于改组时才确认组正确，即(error_1_from != M && error_2_from != M && ........ && error_7_from != M) 时，第M组才算正确。

bemoon
谈谈我对这个问题的分析：
  i_group[6:0] 和 i_frm_map[6:0] 给出了分组和帧是否正确的信息，要求输出组是否正确，输出是o_grp_map。
这个问题可以看成是一个简单的逻辑代数问题。举例而言：
找个一般情况 假设 i_group[6:0]=7‘b0010110；设 i_frm_map的值为X6,X5,X4,X3,X2,X1,X0;
那么o_grp_map可用下述多项式表示：
o_grp_map=5'b00001 & {4'b0000,X0 & X1 & X2}+5'b00010 &{3'b000, (X3 & X4),1'b0}+5'b00100 & {2'b00, X5 ,2'b00}+ 5'b01000 & {1'b0,X6,3'b000};

  上式可以依据与运算分配律展开，归纳得到形如


o_grp_map=Function ( i_group(i),FACTOR(i) & XX(i))  i=0 to 6

的形式

注1：XXi是Xi针对FACTOR的对位展开式，形如{4'b0000,X0 & X1 & X2}，主要是为了“按位与”时不错位；

注2：FACTOR是进位因数，即5'b00001之类；


其中 Function 表示了多项式运算的每个项之间的运算关系，它由i_group(i)决定，若i_group(i)=0则进行“加法”运算，否则进行“按位与”运算。

FACTOR(i)是由i_group决定的5位因数，FACTOR(i) 的取值由i_group的值和FACTOR(i-1) 的值计算得出：



若 i_group[ i ]==1’b0 FACTOR(i)=FACTOR(i-1)*2;

否则 FACTOR(i)=FACTOR(i-1);

针对这种相同形式反复运算的问题，我们可以设计一个运算单元，来描述运算的步骤，最后把这些运算单元串联起来就可以得到结果。分析如下：
令
factor[4:0] 表示 FACTOR；
grp_map[4:0]  表示每步运算结果；
首先根据需求，至少有一个组，所以i_group[0] 总是1，所以设factor[0]=5'b00001，grp_map[0]={4’b0000,X0}；
下一个i_group[1]，若为0，说明有新的组，则
factor[1]=factor[0]*2，grp_map[1]=grp_map[1] + grp_map[0];

反之，若为1 ，则说明是同一组的数据，则
factor[1]=factor[0]，grp_map[1]=grp_map[1] & grp_map[0];

运用数学归纳法可知，对于任意i_group[ i ]，上述推理均成立，且最后一个grp_map就是所求的o_grp_map。
依据上述分析，可以设计如下运算单元：
运算单元输入： i_group[ i ],i_frm_map[ i ],prev_grp_map,prev_factor;//输入上个单元的结果和因子。
运算单元输出：next_grp_map,next_factor;//输出下个单元的结果和因子。
运算单元设计：
/////////////////代码如下/////////////
`GRP_NUM 4

module cell(grp,

frm,

prev_grp_map,

prev_factor,

next_grp_map,

next_factor

);

input wire grp,frm;

input wire   [`GRP_NUM:0] prev_grp_map,prev_factor;

output wire [`GRP_NUM:0] next_grp_map,next_factor;

wire [`GRP_NUM:0] temp_in_grp;

wire [`GRP_NUM:0] temp_at_grp;

assign next_factor=!grp?prev_factor<<1:prev_factor;

assign temp_in_grp=frm?(`GRP_NUM+1)'b1:!next_factor;

assign temp_at_grp=frm?next_factor:(`GRP_NUM+1)'b0;

assgin next_grp_map=!grp?temp_at_grp+prev_grp_map:temp_in_grp&prev_grp_map;

endmodule


   
应用时，因为i_group[0]总是0 ，所以例化6个计算单元即可，初始输入值为grp0=i_group[1];frm0=i_frm_map[1];prev_factor0=5'b00001; prev_grp_map0={4'b0000,i_frm_map[0]};依次连接各个单元的对应端口。最后一个单元的输出就是o_gpr_map。

时间关系，没有测试，个人感觉问题不大。不好意思。

这种做法扩展起来比较方便，随便多少帧多少组都可以，只要修改GRP_NUM，再多例化几个单元就行了。如果嫌例化写起来麻烦，写代码时推荐用verilog 2000 的generator block 可以用for语句例化很省事。或者用VPP等软件做预处理也可以。

最后说一句，如果时序不紧张，最好还是用时序电路来做。虽然组合电路快，一个时钟出结果，但是其中可能的竞争冒险很多，电路的可靠性需要后端来保证。

ksniper

mark

lwy86

mark