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.     

Josephson shift registers

A review of Josephson shift-register circuits that have been designed, fabricated, or tested is presented with emphasis on work in the 1980s. Operating speed is most important, since it often limits system performance. Older designs used square-wave clocks, but most modern designs use offset sine waves, with either two or three phases. Operating margins and gate bias uniformity are key concerns. The fastest measured Josephson shift register operated at 2.3 GHz, which compares well with a GaAs shift register that consumes 250 times more power. The difficulties of high-speed testing have prevented many Josephson shift registers from being operated at their highest speeds. Computer simulations suggest that 30-GHz operation is possible with current Nb/Al ₂O₃/Nb technology. Junctions with critical current densities near 10 kA/cm² would make 100-GHz shift registers feasible     

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.     

Clock-controlled shift registers: a review

Key-stream generators are discussed in which shift registers are clocked in a quasi-random manner under the control of other shift registers. They are a promising practical alternative to those using nonlinear combining functions on the outputs from regularly stepped shift registers and are now almost as well understood. Some World War II ciphers using stuttered rotors are briefly described as natural predecessors, including one cryptanalyzed on the Colossus machines. The algebraic theory is discussed, from which it is shown how large periods and linear equivalences can readily be obtained. The work of a number of authors on cascades is reviewed; these are linear hierarchies in which each register except the first is clock controlled by its predecessor. Other schemes are considered. Results on statistical properties and autocorrelation functions are quoted.<>     

CMOS/SOS semi-static shift registers

Complementary metal-oxide-semiconductor (CMOS) technology has been combined with thin silicon on sapphire films (SOS) for the fabrication of shift registers designed for full TTL compatibility d.c. storage capability, 20 MHz operating frequency, single phase clock and data inputs, and double rail data outputs. Typical power dissipation levels were on the order of 500 nW per stage during standby and 250 /spl mu/W per stage when operating at 20 MHz.     

规则序列与奇异非线性移存器：——求解快速自启动反馈函数

本文提出由非线性移存器产生规则序列的问题，它的用途之一是可以用来取代移位计算器传统的逻辑设计。研究表明，求解快速自启动产生规则序列这一问题其实质就是要寻找一个或一批奇异非线性移存器，且使它或它们的状态力仅有一个带若干短枝的圈。文中用状态转移变换的方法证明了一批快速自启动产生规则序列的奇异非线性移存器。     

Experimental investigation of RSFQ circular shift registers

Circular shift registers (CSRs) can be used in the implementation of superconducting digital signal processing blocks requiring the storage of data that needs to be accessed periodically with short access times and high throughput rate. The clock distribution networks of these shift registers has the unique constraint that the overall clock skew must be zero. Centered around this requirement, a design methodology for the design of these circuits has previously been developed and presented, resulting in three different designs for 64-bit versions of CSRs. We now present experimental results of the functional testing of two of these designs. These results show correct operation up to 13 GHz and set an important step for the complete validation of the design methodology presented earlier.     

Incomplete charge transfer in IGFET bucket-brigade shift registers

The time evolution of the charge transfer during one half-cycle of operation of an IGFET bucket-brigade dynamic shift register is calculated analytically for a smooth but otherwise arbitrary voltage driving function. Wentzel-Kramers-Brillouin-Jeffreys (WKBJ) solutions to the charge transfer equation are matched to Airy-function solutions in the current cutoff region to determine the charge transferred as a function of initial charge. This directly gives several contributions to the incomplete transfer parameter α, the rate of change of the charge left behind on transfer with the initial charge. Although the increment of charge not completely transferred is less than 1 percent of the charge comprising the signal, the calculation is done so that no subtraction of nearly equal large numbers is necessary. We do not evaluate the actual loss of charge due to leakage, traps, recombination, etc. It is found that the finite dynamic drain conductance of an IGFET makes a major contribution to the parameter α, and that under many experimental conditions it will limit shift-register performance. It is also found that all contributions to α depend on the clock-voltage wave-form. Comparison is made with the results of preliminary experiments, and good qualitative and reasonable quantitative agreement is obtained.     

Analog performance limitations of charge-transfer dynamic shift registers

Charge transfer dynamic shift register operation is described and a linearized analysis presented to relate the charge transfer properties to the performance of an n-stage register. An approximate small signal equivalent circuit is also derived to illustrate the similarities to a matched transmission line and the reactive and resistive elements of the line are related to charge transfer and loss characteristics of each stage of the register. The results are expected to be applicable to charge coupled devices and shift registers based on bucket brigade electronics.     

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.     

Linear feedback shift registers as vector quantisation codebooks

Linear feedback shift registers with fixed initial conditions can be used as codebooks for vector quantisation data compression methods, avoiding the need to store codebooks at the encoder and decoder. Suboptimal search procedures can be used to effectively search the codebook space with lower complexity, with only modest coding performance penalties     

High-temperature superconducting shift registers operating at up to100 GHz

Shift registers have been demonstrated in YBaCuO operating at 77 K using from 64 to over 1000 junctions. These are some of the larger scale integrated circuits demonstrated to date using YBaCuO Josephson technology. The circuit is a modified rapid single flux quantum design in which a single trigger pulse causes a one bit shift of the entire word of 32-512 b in length. Two different junction technologies, electron-beam defined nanobridges and epitaxial edge junctions, have been used with parameter spreads ranging from 11% to 22%. Correct operation has been verified with low speed random word tests and circulating data tests while pseudo random bit sequence demonstrations are underway. A practical amount of time to shift between cells has been measured to be about 10 ps     

Group parity prediction scheme for concurrent testing of linear feedback shift registers

A group parity prediction scheme which can be used for concurrent testing of linear feedback shift register circuits is described.     

Performance evaluation of a general framing circuit using two N-stage shift registers

A general algorithm is presented for computing the average number of shifts per frame period (A) of a framing circuit which checks for N consecutive data bits for possible framing bit candidacy. A simulation program has also been written to compute A for N between 2 and 8.     

A generalized Euclidean algorithm for multisequence shift-registersynthesis

The problem of finding a linear-feedback shift register of shortest length capable of generating prescribed multiple sequences is considered. A generalized Euclidean algorithm, which is based on a generalized polynomial division algorithm, is presented. A necessary and sufficient condition for the uniqueness of the solution is given. When the solution is not unique, the set of all possible solutions is also derived. It is shown that the algorithm can be applied to the decoding of many cyclic codes for which multiple syndrome sequences are available. When it is applied to the case of a single sequence, the algorithm reduces to that introduced by Y. Sugiyama et al. (Inf. Control, vol.27, p.87-9, Feb. 1975) in the decoding of BCH codes     

EIGNVALUE SHIFT SUPPERRESOLUTION ALGORITHM

This paper provides a new approach to spatial spectral estimation, called eigenvalue shift superresolution algorithm. This method avoids the inverse covariance matrix. It can be applied to the processing of data received by spatially distributed array of sensors.     

400 dpi integrated contact type linear image sensors with poly-SiTFT's analog readout circuits and dynamic shift registers

Four-hundred-dots-per-inch (dpi) sensors, including poly-Si thin-film-transistor (TFT) scanning circuits, and a-Si photodiodes fabricated on borosilicate glass have been developed. This contact-type image sensor contains TFT analog buffer amplifiers in the readout circuits. The scanning circuits can operate in a frequency range between 200 kHz and 1 MHz. The readout circuits incorporating TFT analog impedance converters decrease photodiode impedance by more than three orders of magnitude and improve the linearity between illumination intensity and the sensor output. High-resolution reading is achieved by the new contact-type linear image sensors with a storage time of 2 ms/line     

带宽自适应Mean Shift跟踪算法

提出了一种先进行空间定位再确定目标尺度的两级跟踪算法,有效地解决了mean shift算法对尺度变化的适应问题.该算法首先在当前帧对应位置进行降分辨率处理,并以基于增量试探的mean shift跟踪算法收敛点作为当前帧目标中心位置,进而利用对数极坐标变换的旋转、尺度不变性,对目标和候选目标分别进行对数极坐标映射,并通过求取最大归一化相关函数确定目标的尺度变化.跟踪实验表明,该算法可以有效的提高mean shift跟踪算法空间和尺度定位准确性.