任意偶数长度Gray码序列及其在异步FIFO设计中的应用

任意偶数长度Gray码序列及其在异步FIFO设计中的应用 任意偶数长度的Gray码序列，在异步FIFO设计中，只需要对控制逻辑做少量的改动即可得到任意偶数深度的异步FIFO。在保持性能不变的前提下，改进后的异步FIFO能明显减少电路面积。

1、任意偶长度Gray码序列的存在性及构造方法 （1）首先证明对于任意奇数N，不存在长度为N的Gray序列。 不失一般性，假设存在任意长度为奇数N的Gray码序列，且以全0为起点。序列中N个编码映射到立方体的N个顶点；有Gray码的定义可知N个点之间可以建立一条哈密尔顿回路，任意两个相邻顶点的坐标有且只有一位不同。 回路全由全0出发，最后又回到全0，说明在回路的某个位置上有一位发生翻转（0—1 或1—0），则必定在回路的另一个位置该位发生相反的翻转。也就是说必定发生了偶数次的翻转，即回路长度N应该为偶数。

（2）对于偶数N，必定存在长度为N的Gray序列 当N=2^n时，该命题成立。下面证明对非2的幂次方的偶数该命题也成立。

假设2^(n-1) < N < 2 ^ n，以长度为2 ^n的BRGC序列为基础使用构造法证明。

2、构造         （1）对称裁剪法 长度为2^n的格雷码序列中的第i个与第（2 ^n - i -1）个元素只有最高位不同。则，以长度为2 ^ n的格雷码序列为基础，①对称地去掉第N/2 ~ (2 ^ n - N/2 -1)这些元素，或②对称的去掉第0~(2 ^ n - N/2 -1)和第(2 ^ n + N/2) ~ (2 ^ n -1)这些元素。则1剩余的元素组成长度为N的Gray序列。

        （2）Gray面裁剪法 长度为2n的BRGC序列对应的立方体中，各个Gray面中各顶点编码的最低两位表现为00–01–11–10或10–11–01—00的循环。进一步观察可以发现：00和10其实也只有1位不同；即每个Gray面中去掉中间两个顶点，其第一个顶点（上一个Gray面进入该面的入口顶点）和最后一个顶点（该Gray面到下一个Gray面的出口顶点），也符合格雷码序关系，而不影响其它Gray面。

因此我们得出构造长度为N的Gray码序列的又一种方法；在长度为2^n的BRGC序列所映射的立方体中，任意找出其中的2 ^ (n-1) – N/2个Gray面，挖掉这些Gray面中的中间两个顶点，则剩余顶点组成长度为N的Gray码序列。

为了尽量减少对传统异步FIFO设计的修改，改进的异步FIFO只对Gray码编码模块做少量修改，而空满状态判断逻辑保持不变。

主要修改为： （1）条件加法器 二进制加法器中增加条件判断逻辑，并经过触发器（该触发器初始化为1）延迟后再进行BRGC编码。这样可以避免修改BRGC编码以及空满判断逻辑；并减少关键路径的长度，使性能不至于下降。

（2）存储体索引指针 存储体索引指针不再直接取二进制加法器输出的低位端，而要根据具体的条件进行加减操作生成。