首页> 外文期刊>IEEE Transactions on Computers >Analysis and Efficient Implementations of a Class of Composited de Bruijn Sequences
【24h】

Analysis and Efficient Implementations of a Class of Composited de Bruijn Sequences

机译:一类Composited de Bruijn序列的分析和有效实施

获取原文
获取原文并翻译 | 示例

摘要

A binary de Bruijn sequence is a sequence of period 2(n) in which every binary n-tuple occurs exactly once in each period. A de Bruijn sequence has good randomness properties, such as long period, ideal tuple distribution, and high linear complexity, and can be generated by a nonlinear feedback shift register (NLFSR). Finding an efficient NLFSR that can generate a de Bruijn sequence with a long period is a significant challenge. "Composited construction" is a technique for constructing a de Bruijn sequence of period 2(n+k) by an NLFSR from a de Bruijn sequence of period 2(n) through a composition operation repeatedly applying k times. The goal of this article is to further investigate the composited construction of de Bruijn sequences with efficient hardware implementations, and determine randomness properties such as linear complexity. Our contributions in this article are as follows. First, we present a generalized construction of composited de Bruijn sequences that is constructed by adding a combination of conjugate pairs of different lengths in the feedback function of the composited construction, which results in generating a class of de Bruijn sequences of size 2(k), whereas the original composited construction can generate only two sequences. Second, we investigate the linear complexity and the correlation property of the new class of de Bruijn sequences. We prove theoretically that the linear complexity of this class of de Bruijn sequences is optimal or close to optimal. Interestingly, we also prove that the linear complexities of all the sequences of this class are equal, which strengthens Etzion's conjecture (JCTA 1985, IEEE-IT 1999) about the number of de Bruijn sequences with equal linear complexity. This is the first known construction of de Bruijn sequences of an arbitrarily long period whose linear complexities are determined theoretically. Finally, we implement our construction in hardware to demonstrate its practicality. We synthesize our implementations for a 65 nm ASIC and a Xilinx Spartan FPGA and present hardware areas, and performances of de Bruijn sequences of periods in the range of 2(160) to 2(1056). For instance, a class of de Bruijn sequences of period 2(160) (resp. 2(288)) can be implemented with an area of 3.43 (resp. 6.71) kGEs in 65 nm ASIC, and 83 (resp. 229) slices in Spartan6 FPGA.
机译:二进制de bruijn序列是一个周期2(n)的序列,其中每个二进制n-cuple在每个时段中完全发生一次。 de Bruijn序列具有良好的随机性属性,例如长时段,理想的元组分布和高线性复杂性,并且可以由非线性反馈移位寄存器(NLFSR)生成。找到一个有效的NLFSR,可以在长期内生成De Bruijn序列是一个重大挑战。 “计算施工”是通过通过组合操作重复施加K次的组成操作,通过从DE Bruijn序列(N)的De Bruijn序列由NLFSR构成De Bruijn序列的技术序列2(n + k)。本文的目标是进一步调查与有效的硬件实现的De Bruijn序列的合作结构,并确定随机性属性,例如线性复杂性。我们本文的贡献如下。首先,我们介绍了由在复合结构的反馈函数中添加不同长度的共轭对的组合构成的构建的共同构造,这导致产生大小2(k)的一类De Bruijn序列,而原始的合成结构只能产生两个序列。其次,我们研究了新类别的De Bruijn序列的线性复杂性和相关性。理论上我们证明了这类De Bruijn序列的线性复杂性是最佳的或接近最佳的。有趣的是,我们还证明,该课程的所有序列的线性复杂性是相等的,它加强了etzion的猜想(JCTA 1985,IEEE-IT 1999),其具有相同的线性复杂性的De Bruijn序列的数量。这是第一种已知的任意长时间的Bruijn序列的序列的施工,其线性复杂性在理论上是确定的。最后,我们实施了我们的硬件建设,以展示其实用性。我们为65nm AsiC和Xilinx Spartan FPGA和目前的硬件区域合成了我们的实施,以及De Bruijn序列的性能在2(160)至2(1056)的范围内。例如,期间2(160)的一类De Bruijn序列(RESP。2(288))可以在65nm AsiC中的3.43(RESP.6.1)KGES的面积和83(RESP.229)切片来实现在Spartan6 FPGA。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱:kefu@zhangqiaokeyan.com

京公网安备:11010802029741号 ICP备案号:京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有
  • 客服微信

  • 服务号