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 and Galois representations of feedback-with-carry shiftregisters

A feedback-with-carry shift register (FCSR) with "Fibonacci" architecture is a shift register provided with a small amount of memory which is used in the feedback algorithm. Like the linear feedback shift register (LFSR), the FCSR provides a simple and predictable method for the fast generation of pseudorandom sequences with good statistical properties and large periods. In this paper, we describe and analyze an alternative architecture for the FCSR which is similar to the "Galois" architecture for the LFSR. The Galois architecture is more efficient than the Fibonacci architecture because the feedback computations are performed in parallel. We also describe the output sequences generated by the d-FCSR, a slight modification of the (Fibonacci) FCSR architecture in which the feedback bit is delayed for d clock cycles before being returned to the first cell of the shift register. We explain how these devices may be configured so as to generate sequences with large periods. We show that the d-FCSR also admits a more efficient "Galois" architecture     

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).     

Linear transformation shift registers

In order to exploit word-oriented operations for linear-feedback shift registers (LFSRs), Tsaban and Vishne [2002] introduced the notion of linear transformation shift registers (TSRs). An implementation of their primitive TSR generating algorithm shows that the LFSR are paired for all transformations. We prove that the characteristic polynomials of a pair of LFSRs are either both irreducible or both reducible for all transformations. This allows some time improvement when finding primitive TSRs. The authors give a full enumeration of all primitive TSRs with transformations of order 8 and LFSRs of order 3, 4, 5, and 6.     

FCSR原理及其VHDL语言的实现

伪随机序列发生器是序列密码设计中的重要环节，FCSR是其中一类重要思想。本文介绍了FCSR的特性和产生方法，并用VHDL语言予以实现，给出FCSR序列的主程序和仿真波形，最后指出需要注意的问题。     

一类非线性扩频序列的构造及其性能分析

基于本原三项式线性函数,构造了一类非线性序列.首先根据非线性序列生成规律,借助逻辑代数理论,推导并提取了非线性序列特征函数,利用特征函数筛分作用,合成了非线性反馈函数,据此实现了非线性序列生成.最后,对该类非线性序列特性进行了分析和计算,并将其应用于直接序列码分多址通信系统(DS-CDMA)仿真实验中,结果表明该类非线性序列不仅具有理想的伪随机特性、良好的线性复杂度,还具有优于m序列、gold序列的误码率.     

A Back-Iteration Method for Reconstructing Chaotic Sequences in Finite-Precision Machines

Discrete-valued chaotic sequences, when used as long-period spreading codes or stream ciphers, are expected to offer a low probability of interception and thus an enhancement in security. In this paper, the weakness of digital chaotic sequences is reported. We demonstrate that it is possible to reconstruct a long-period discrete-valued sequence generated by a chaotic system based on very few past values when the sequence generator is implemented in finite-wordlength digital hardware. The proposed back-iteration reconstruction method is based on the connection between the symbolic sequence and the initial condition of a chaotic system. This work was performed when the authors were with the Nanjing Institute of Communications Engineering, Nanjing, Jiangsu Province, 210007, China, supported by the National Science Foundation of China under Grants 69931040 and 60672081, and by the Science Foundation of Jiangsu Province under Grant BK2006502.     

Bounded Real Lemma for Structured Noncommutative Multidimensional Linear Systems and Robust Control

We obtain a standard Bounded Real Lemma and a strict Bounded Real Lemma for the class of input/state/output linear systems with evolution along a free semigroup recently introduced by the authors. As an application we show the equivalence of this result with a recent result from robust control theory: the structured μ-singular value of an operator (taken in a certain uniform sense) is equal to its upper bound computed via diagonal scalings in case the structured singular value is taken with respect to the collection of time-varying perturbations given by a linear-fractional model. Mathematics Subject Classification (2000) Primary: 93D09, Secondary: 13F25, 47A56, 47A60, 93B28 Published online: April 2006 The first author was partially supported by US National Science Foundation under Grant Number DMS-9987636; The second author is supported by the National Research Foundation of South Africa under Grant Number 2053733; The third author was supported by a grant from Naresuan University, Thailand     

Nonparametric spectral analysis of gapped data via an adaptive filtering approach

We present an algorithm for nonparametric complex spectral analysis of gapped data via an adaptive finite impulse response (FIR) filtering approach, referred to as the gapped-data amplitude and phase estimation (GAPES) algorithm. The incomplete data sequence may contain gaps of various sizes. The GAPES algorithm iterates the following two steps: (1) estimating the adaptive FIR filter and the corresponding complex spectrum via amplitude and phase estimation (APES), a nonparametric adaptive FIR filtering approach, and (2) filling in the gaps via a least-squares APES fitting criterion. The initial condition for the iteration is obtained from the available data segments via APES. Numerical results are presented to demonstrate the effectiveness of the proposed GAPES algorithm.This work was supported in part by the Senior Individual Grant Program of the Swedish Foundation for Strategic Research, AFRL/SNAT, Air Force Research Laboratory, Air Force Material Command, USAF, under grant number F33615-99-1-1507, and the National Science Foundation Grant MIP-9457388. The US Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notice thereon.     

An Efficient Deterministic Test Pattern Generator for Scan-Based BIST Environment

To obtain satisfactory fault coverage for testing a logic circuit, linear feedback shift registers (LFSRs) have been used to generate not only the pseudorandom, but also the deterministic patterns in the scan-based built-in self-test environment. However, like other scan-based methods, the LFSR based pattern generation schemes take a long test application time to feed deterministic patterns from the LFSR into a scan chain. In this paper we derive a general relationship between the bits in the scan chain and the states of the LFSR and show that any bit to be generated by an LFSR in any future clock cycle can be pre-generated by a linear function of the current LFSR state. With this relationship, we can divide a scan chain into multiple sub-chains and use one LFSR-based multiple sequence generator to simultaneously generate all the subsequences required by the sub-chains, hence can greatly reduce the test application time for deterministic patterns. Moreover, due to the scan time reduction, test power wasted during the scan operation can also be significantly reduced.     

Polynomial ambiguity resistant precoders: Theory and applications in ISI/multipath cancellation

In this paper, precoding techniques are studied for combating the intersymbol interference (ISI)/multipath effects in communication systems. We introduce a new type-precoder which we term thepolynomial ambiguity resistant (PAR) precoder for its ability to resist signal distortion induced by finite impulse response (FIR) channels. In particular, the precoder allows a receiver to identify an input signal without knowing the channel characteristics at the expense of a minimum amount of bandwidth increase. A family of such precoders, which is linear (no modulo operations), channel independent, and modulation pattern preserving (except for some occasional 0 symbols), is presented. Also presented is a closed-form algorithm that can simultaneously identify the input signals and zero-forcing equalizers.Work supported in part by the Air Force Office of Scientific Research (AFOSR) under Grant No. F49620-97-1-0253 and F49620-98-1-0352, the National Science Foundation CAREER Program under Grant MIP-9703377, and the University of Delaware Research Foundation.Work supported in part by the Air Force Office of Scientific Research (AFOSR) under Grant No. F49620-97-1-0318, the Office of Naval Research (ONR) under Grant No. N00014-97-1-0475, and the National Science Foundation CAREER Program under Grant MIP-9703074.     

PN Sequence Generation from 2‐D Array of Shift Registers

Toward code division multiple access (CDMA) communications and data protection, we propose and analyze pseudorandom noise (PN) sequences generated from a 2‐dimensional array structure of shift‐registers. For any positive integers m and n, we construct PN sequences of period 2^mn–1 using an m×n array of registers and show that we can generate all shifted PN sequences as required by IS‐95x with the proper linear combination of available sequences.     

联合的F-FCSR密钥流生成器

 在分析带进位反馈移位寄存器(FCSR)的滤波密钥流生成器族F-FCSR线性弱点和其硬件方案F-FCSR-Hv2被攻破原因基础之上,提出了利用两个F-FCSR输出简单非线性运算而成的联合的F-FCSR密钥流生成器.该生成器避免了利用该种情况而进行的Hell-Johansson攻击,其生成序列通过了美国技术与标准局(NIST)STS的16项随机性测试,有高的复杂度,且能抵抗相关攻击和代数攻击.     

Design and fabrication of sub-μs silicon-on-insulator thermo-optic 4×4 switch matrix

A rearrangeable nonblocking silicon-on-insulator-based thermo-optic 4x4 switch matrix with spot size converters （SSCs） and a new driving circuit are designed and fabricated. The introduction of a spot size converter （SSC） has decreased the insertion loss to less than 10dB and the new driving circuit has improved the response speed to less than l~s.     

A parallel algorithm for evaluating general linear recurrence equations

A block parallel partitioning method for evaluating general linearmth order recurrence equations is presented and applied to solve the eigenvalues of symmetric tridiagonal matrices. The algorithm is based on partitioning, in a way that ensures load balance during computation. This method is applicable to both shared memory and distributed memory MIMD systems. The algorithm achieves a speedup ofO(p) on a parallel computer withp-fold parallelism, which is linear and is greater than the existing results, and the data communication between processors is less than that required for other methods. For solving symmetric tridiagonal eigenvalue problems, our method is faster than the best previous results. The results were tested and evaluated on an MIMD machine, and were within 79% to 96% of the predicted performance for the second order linear recurrence problem.Supported by the Texas Advanced Technology Program under Grant No. 999903-165 and the National Science Foundation under Grant No. MIP8809328.     

Ladder networks,fixpoints, and the geometric mean

Using fixed-point arguments, existence and uniqueness results are obtained for the joint resistance of infinite positive operator networks with noncommuting operators in the branches. Explicit representations for the joint resistance are given using the geometric mean of positive operators.This research was supported by the National Science Foundation under Grant MCS 80-01906.     

Linear complexity of a type of clock-controlled sequence

A new type of cascaded clock-controlled system is proposed. There are r+1 linear feedback shift registers (LFSRs) of length n in the system if the degree of cascade connection is r. It is proved that for an rth degree cascade the output sequences have linear complexity n Sigma /sub i=0//sup r/ (2/sup n/-1)/sup i/, period (2/sup n/-1)/sup r+1/ and good statistical properties. Such a model can generate key stream sequences of stream ciphers in computer applications.<>     

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%.     

Signal and image processing using three-dimensional binary ranking transforms

Because binary mathematical morphology permits fast local neighborhood operations by flash conversion, it is used extensively in high-speed pattern-recognition computer systems. Further, since anyN-dimensional integer function may be represented by an (N + 1)-dimensional binary (bilevel) function, ordinary two-dimensional graylevel images become three-dimensional binary images. Thus these images may be processed by high-speed flash-conversion computers assuming that a sufficiently compact three-dimensional kernel can be devised. The tetradekahedron of the face-centered-cubic tessellation forms a perfect kernel in three-dimensions. Its neighborhood is compact. It has total symmetry with all 12 neighbors equidistant from the central element. Using this kernel a variety of useful three-dimensional morphological operations may be performed for target track detection, shaded graphics, data clustering, automated focusing, and spatial filtering.This research was supported by the National Cancer Institute (Grant CA45047), the National Science Foundation (Grant DCR8611863), the Office of Naval Research (Contract Number N001488K-0435-N143), and the Department of Defense (delivery order 00055, San Diego State University Foundation, under Contract 85-D0203 from the Naval Ocean Systems Center).     

Pseudonoise sequences based on algebraic feedback shift registers

Over the past half century, various statistical properties of pseudorandom sequences have played important roles in a variety of applications. Among these properties are Golomb's randomness conditions: (R1) balance, (R2) run property, and (R3) ideal autocorrelations, as well as the closely related properties (R4) shift and add, and (R5) de Bruin (uniform distribution of subblocks). The purpose of this paper is to describe the relationships among these conditions, and to introduce a new method for generating sequences with all these properties, using algebraic feedback shift registers.