Partial period distribution of FCSR sequences

Klapper and Goresky (1995) introduced feedback with carry shift register (FCSR) and presented a significant kind of FCSR sequences, that is, l-sequences. They showed that the number of 0s and 1s occurring in one of their periods are equal. We discuss the partial period distribution of l-sequences, and show that when the periods become large, the proportion of 1s (resp., 0s) occurring in any of their partial periods approximates 50%.     

Feedback with carry shift registers synthesis with the Euclidean algorithm

Feedback with carry shift registers (FCSR) were introduced by Klapper and Goresky (1994). They are very similar to classical linear feedback shift registers (LFSR) used in many pseudorandom generators. The main difference is the fact that the elementary additions are not additions modulo 2 but with propagation of carries. The mathematical models for LFSR are equivalently linear recurring sequences over GF(2) or rational series in the set GF(2)[[x]]. For FCSR, the "good" model is the one of rational 2-adic numbers. It is well known, that the series generated by a LFSR can be synthesized by either the Berlekamp-Massey algorithm for binary linear recurring sequences or the extended Euclidean algorithm in the set GF(2)[x] of binary polynomials. Klapper and Goresky (1997) give an algorithm for the FCSR synthesis. This algorithm is similar to those of Berlekamp-Massey and is based on De Weger and Mahler's rational approximation theory. In this correspondence, we prove that it is possible to synthesize the FCSR with the extended Euclidean algorithm in the ring /spl Zopf/ of integers. This algorithm is clearly equivalent to the previous one, however, it is simpler to understand, to implement, and to prove. Our algorithm is still valid in the case of g-adic integers where g is a positive integer. We also give a near-adaptative version of this algorithm.     

一种可重构线性反馈移位寄存器设计

提出了一种可重构线性反馈移位寄存器的设计。在设计中,针对Fibonacci和Galois两种类型的反馈结构分别采用了可重构的设计,并且支持混合反馈结构,线性反馈移位寄存器反馈抽头和插入点可选,长度可变并且可以通过链接支持超长线性反馈移位寄存器。在XC5VLX30器件上实现延时为4.808ns,LUT和触发器的个数为2279和1575。能够用于伪随机序列生成等应用。     

高速线性反馈移位寄存器的实现

线性反馈移位寄存器（ＬＦＳＲ）被广泛用于扩频通信，内建自测试和数字加密等许多领域。文中针对这一类电路的物理实现，提出了利用动态双边沿触发器实现高速线性反馈移位寄存器的一种新型结构。在不增加电路代价的前提下，获得了两倍于传统主－从铁速度，在此基础上，提出双相并行结构，从理论上分析，可得到最高的移位速度。     

On the linear complexity of nonlinearly filtered PN-sequences

Binary sequences of period 2/sup n/-1 generated by a linear feedback shift register (LFSR) whose stages are filtered by a nonlinear function, f, are studied. New iterative formulas are derived for the calculation of the linear complexity of the output sequences. It is shown that these tools provide an efficient mechanism for controlling the linear complexity of the nonlinearly filtered maximal-length sequences.     

Design Algorithm of All-Optical Linear Feedback Shift Registers

We demonstrate an algorithm for the design and implementation of an all-optical linear feedback shift register (LFSR), based on optically controlled XOR gate and optical shift registers. The algorithm tackles the huge length of optical shift registers to produce controllable pseudorandom binary sequences (PRBS).     

基于FCSR的双滤波密钥流生成器

当前,由于还没有一个适于一般目的的流密码国际加密标准,流密码的设计与分析引起了广泛关注。在以前的流密码的设计中多采用线性反馈移位寄存器（LFSR）作为基本的部件。然而由于LFSR本身的线性性,基于LFSR的流密码备受攻击,进而相继出现了一些替换部件,例如T函数,带进位的反馈移位寄存器（FCSR）等等。文中给出了一个新的基于FCSR的密钥流生成器。理论分析表明该密钥流生成器具有高度的安全性。NIST统计测试表明该密钥流生成器的伪随机特性是理想的。     

一种新的低功耗内建自测法 􀀂 􀀂 􀀂 线性反馈移位寄存器结构的更改

本文提出了一种通过改变线性反馈移位寄存器（LFSR）的结构实现低功耗内建自测试方法。在伪随机测试方式下，随着测试的进行，测试矢量的效率大幅降低。通过改变线性反馈移位寄存器的结构滤掉无效的测试矢量从而实现低功耗测试。实践证明，改变线性反馈称位寄存器的结构的方法是有效的并且对故障覆盖率没有影响。     

Design of test sequences for VLSI self-testing using LFSR

Consider a shift register (SR) of length n and a collection of designated subsets of {0,1, . . ., n-1}. The problem is how to add feedback to the SR such that the resulting linear feedback shift register (LFSR) exercises (almost) exhaustively each of the designated subsets and is of small period. Several previously known results for maximum-length LFSR are extended to more general LFSR, and in particular a previously known algorithm is simplified and extended. Applications to the problems of VLSI self-testing are discussed and illustrated     

Some Results on FCSR Automata With Applications to the Security of FCSR-Based Pseudorandom Generators

This article describes new theoretical results concerning the general behavior of a feedback with carry shift register (FCSR) automaton. They help to better understand how the initial parameters must be chosen to use this automaton as a basic block of a filtered stream cipher. These results especially concern the structure of the transition graph of an FCSR automaton and the number of iterations of the FCSR transition function required to reach the main part of the graph. A potential linear weakness and a easy way to prevent the corresponding attack are also given.     

Pseudo noise sequences for engineers

Pseudo random binary sequences (PRBSs), also known as pseudo noise (PN), linear feedback shift register (LFSR) sequences or maximal length binary sequences (m-sequences) are widely used in digital communications and the theory involved has been treated extensively in the literature. However, a practising engineer is interested in the fundamentals and the applications of PN sequences, and the methods of generating them with hardware. This paper presents, without the mathematical rigours, some of the interesting characteristics and the use of these characteristics in the generation and acquisition of PN sequences. The series-parallel method of generating PN sequences at high speeds with low-speed devices, which is of interest to hardware designers, is discussed. Some applications of PN sequences in communications and instrumentation are discussed     

Reducing test-data volume and test-power simultaneously in LFSR reseeding-based compression environment

This paper presents a new test scheme based on scan block encoding in a linear feedback shift register (LFSR) reseeding-based compression environment.Meanwhile,our paper also introduces a novel algorithm of scan-block clustering.The main contribution of this paper is a flexible test-application framework that achieves significant reductions in switching activity during scan shift and the number of specified bits that need to be generated via LFSR reseeding.Thus,it can significantly reduce the test power and test data volume.Experimental results using Mintest test set on the larger ISCAS’89 benchmarks show that the proposed method reduces the switching activity significantly by 72%-94%and provides a best possible test compression of 74%-94%with little hardware overhead.     

Feedback shift registers, 2-adic span, and combiners with memory

Feedback shift registers with carry operation (FCSRs) are described, implemented, and analyzed with respect to memory requirements, initial loading, period, and distributional properties of their output sequences. Many parallels with the theory of linear feedback shift registers (LFSRs) are presented, including a synthesis algorithm (analogous to the Berlekamp-Massey algorithm for LFSRs) which, for any pseudorandom sequence, constructs the smallest FCSR which will generate the sequence. These techniques are used to attack the summation cipher. This analysis gives a unified approach to the study of pseudorandom sequences, arithmetic codes, combiners with memory, and the Marsaglia-Zaman random number generator. Possible variations on the FCSR architecture are indicated at the end. Andrew Klapper was sponsored by the Natural Sciences and Engineering Research Council under Operating Grant OGP0121648, the National Security Agency under Grant Number MDA904-91-H-0012, and the National Science Foundation under Grant Number NCR9400762. The United States Government is authorized to reproduce and distribute reprints notwithstanding any copyright notation hereon. Mark Goresky was partially supported by the Ellentuck Fund and National Science Foundation Grant Number DMS 9304580.     

An effective logic BIST scheme based on LFSR-reseeding and TVAC

An effective logic built-in self-test scheme aiming at reducing the area overhead of IC testing and improving the fault average is proposed, which combines strategies of linear feedback shift register (LFSR)-reseeding with test vectors applied by circuit-under-test itself (TVAC). LFSR-reseeding technology is first applied to decrease the size of test set and the number of interior feedback wires, while TVAC technology is applied to decrease the number of stored seeds. An efficient LFSR-reseeding algorithm and a modified quick judgment method for path search are proposed. Experimental results for ISCAS 85 benchmarks demonstrate that the proposed method reduces the number of interior feedback wires more than 50% on average and can achieve full fault coverage with much less groups as well as area overhead compared with previous TVACs.     

全动态密钥流生成器DF-FCSR-8

研究了基于带进位的反馈移位寄存器(FCSR)滤波的密钥流生成器族(F-FCSR),在分析F-FCSR线性弱点和F-FCSR-Hv2被攻破原因的基础之上,提出了全动态滤波密钥流生成器DF-FCSR-8。避免了利用该种情况而进行的Hell-Johansson攻击。其生成序列通过了美国技术与标准局(NIST)STS软件包的16项随机性测试,有良好的随机性。同时生成器也能抵抗其他攻击。     

A General Construction of Tweakable Block Ciphers and Different Modes of Operations

This work builds on earlier work by Rogaway at Asiacrypt 2004 on tweakable block cipher (TBC) and modes of operations. Our first contribution is to generalize Rogaway's TBC construction by working over a ring and by the use of a masking sequence of functions. The ring can be instantiated as either GF or as . Further, over GF, efficient instantiations of the masking sequence of functions can be done using either a binary linear feedback shift register (LFSR); a powering construction; a cellular automata map; or by using a word-oriented LFSR. Rogaway's TBC construction was built from the powering construction over GF. Our second contribution is to use the general TBC construction to instantiate constructions of various modes of operations including authenticated encryption (AE) and message authentication code (MAC). In particular, this gives rise to a family of efficient one-pass AE modes of operation. Out of these, the mode of operation obtained by the use of word-oriented LFSR promises to provide a masking method which is more efficient than the one used in the well known AE protocol called OCB1.     

Thermal Noise Random Number Generator Based on LFSR

With the rapid development of cryptography, the strength of security protocols and encryption algorithms consumedly relies on the quality of random number. In many cryptography applications, higher speed is one of the references required. A new security random number generator architecture is presented. Its philosophy architecture is implemented with FPGA, based on the thermal noise and linear feedback shift register（LFSR）. The thermal noise initializes LFSRs and is used as the disturbed source of the system to ensure the unpredictability of the produced random number and improve the security strength of the system. Parallel LFSRs can produce the pseudo-random numbers with long period and higher speed. The proposed architecture can meet the requirements of high quality and high speed in cryptography.     

A 3$,times,$5-Gb/s Multilane Low-Power 0.18-$mu{hbox {m}}$ CMOS Pseudorandom Bit Sequence Generator

A low-power, three-lane, pseudorandom bit sequence (PRBS) generator has been fabricated in a 0.18-mum CMOS process to test a multilane multi-Gb/s transmitter that cancels far-end crosstalk. Although the proposed PRBS generator was designed to produce three uncorrelated 12-Gb/s PRBS sequences, measurement results included in this paper have been obtained at only 5 Gb/s due to test setup limitations. The prototype employs a CMOS latch optimized to operate at frequencies close to the of the process and a current-mode logic (CML) MUX with modified active inductor loads for better high-speed large-signal behavior. In order to reduce the power consumption, a quarter-clock rate linear feedback shift register (LFSR) core in a power-efficient parallel architecture has been implemented to minimize the use of power-hungry, high-speed circuitry. Further power reduction has been achieved through the clever partitioning of the system into static logic and CML. In addition, the prototype design produces three uncorrelated 12-Gb/s data streams from a single quarter-rate LFSR core, thereby amortizing the power across multiple channels which lowers the power per channel by 3 times. The total measured power consumption at 5 Gb/s is 131 mW per lane and the calculated figure of merit per lane is 0.84 pJ/bit, which is significantly better than previously published designs.     

CRT-Based High-Speed Parallel Architecture for Long BCH Encoding

Bose–Chaudhuri–Hocquenghen (BCH) error-correcting codes are now widely used in communication system and digital technology. The direct linear feedback shifted register (LFSR)-based encoding of a long BCH code suffers from the large fan-out effect of some xor gates. This makes the LFSR-based encoders of long BCH codes not keep up with the data transmission speed in some applications. The technique for eliminating the large fan-out effect by J-unfolding method and some algebraic manipulation has been proposed. In this brief, we present a Chinese remainder theorem (CRT)-based parallel architecture for long BCH encoding. Our novel technique can be used to eliminate the fan-out bottleneck. The only restriction on the speed of long BCH encoding of our CRT-based architecture is $log_{2}N$, where $N$ is the length of the BCH code.      

Bit-swapping LFSR for low-power BIST

A modified linear feedback shift register (LFSR) is presented that reduces the number of transitions at the inputs of the circuit-under-test by 25% using a bit-swapping technique. Experimental results on ISCAS'85 and 89 benchmark circuits show up to 45% power reduction during test. They also show that the proposed design can be combined with other techniques to achieve a very substantial power reduction of up to 63%.