Cyclotomics, Inc.

Eastman-kodak Company

Unisys Corporation

Elwyn R Berlekamp

Po Tong

Lloyd R Welch

Gadiel Seroussi

James U Lemke

James A Bixby

Robert J Currie

Craig K Rushforth

Estimates of the horizontal and vertical positions of digital bits on film are corrected by tracking the bit transition boundaries in the horizontal and vertical directions. Frequency of useful film bit transitions in the vertical direction is maximized prior to recording by error correction encoding the digital audio bytes using a symmetrical generator polynomial and then selectively inverting symmetric portions of each codeword. Frequency of useful film bit transistions in the horizontal direction is maximized prior to recording by channel encoding the error correction symbols in each codeword so as to force the weight of the resulting symbol to be half the number of data bits per symbol.

Digital optical sound system

Estimates of the horizontal and vertical positions of digital bits on film are corrected by tracking the bit transition boundaries in the horizontal and vertical directions. Frequency of useful film bit transitions in the vertical direction is maximized prior to recording by error correction encoding the digital audio bytes using a symmetrical generator polynomial and then selectively inverting symmetric portions of each codeword. Frequency of useful film bit transitions in the horizontal direction is maximized prior to recording by channel encoding the error correction symbols in each codeword so as to force the weight of the resulting symbol to be half the number of data bits per symbol.

A Reed-Solomon decoder is implemented in systolic arrays wherein clock and control information propagate serially with the data. Progressive loss of coherence in such arrays is compensated by a folded array structure symmetrized in clock control whereby coherence is progressively re-established at the output of each such array.

Hypersystolic Reed-Solomon decoder

Transmitting and receiving apparatus for transmitting data which includes a purged extended Golay (22,7) code encoder at the transmitter for encoding digital data into constant weight unbalanced codewords representative of the digital data. The constant weight unbalanced codewords contain error correction bits and are preferably transmitted as balanced codewords. When the receiver decodes the original digital data, improved tracking and acquisition of the transmitted data is achieved.

Coder-decoder for purged extended golay (22,7) codes

In an error trapping decoder in which a received codeword is shifted through a re-encoder shift register to produce a set of r syndrome characters and in which the encoder shift register is then isolated and its contents shifted until a number of consecutive zero virtual check characters is produced therein, the capacity to trap long error bursts is enhanced by increasing the size of the code and by demanding that the minimum number of consecutive zero virtual check characters be only sufficient to ensure an acceptably low probability that one or more of the zero-value virtual check characters is a false indication. Such a decoder may be used to determine the location of an error burst in a received block of interleaved codewords as long as at least one of the codewords in the block produces the minimum number of consecutive zero-value virtual check characters after a requisite number of shifts of the encoder. Upon this occurrence, the codeword locations of the non-zero-value virtual check characters are designated as erasure locations for the rest of the codewords in the block, thus enabling all of them to be decoded.

Elongated burst trapping

In a Reed-Solomon Decoder, each byte of a received codeword is matched to the closest resembling one of a set of allowed symbols and assigned a certain reliability, reflecting the degree of resemblance. The symbols thus matched are arranged in descending order to reliability to form a virtual codeword, the first K symbols being virtual message bytes and the remaining r symbols being virtual check bytes. The virtual codeword is then decoded using an algorithm which produces a series of iterative approximations to the transmitted codeword. The approximation most closely resembling the received codeword is selected as the corrected codeword.

Soft decision Reed-Solomon decoder

In a multi-channel device for the processing of digital data bytes comprised of parallel arrangements of data bits, the invention calls for recognition of the fact that--irrespective of skew and other interchannel variations in the processing of such data bits--the median-occurring bit of each successive data byte constitutes a good representative of the time of occurrence of the byte in question. By suitably buffering the bits of successive data bytes, a 'median clock' that is slaved to the aforenoted 'median-occurring' bits may be used to clock data bytes--devoid of inter-channel timing errors--out of the apparatus used for the indicated buffering operation.

Digital time base correction using a reference bit

In a multi-channel apparatus, a first plurality of N channels support user data and associated error correction and a second plurality of channels each contain a unique p-bit symbol followed by N consecutive M-bit samples of each of the N data channels. The receiver or retriever apparatus regenerates a system clock from all channels and examines the respective bit streams to score each bit phase as a match or a non-match of the sample in the synch channel with each M bit sample of the respective N data streams, and for each such N channels a counter corresponding to the then current phase is incremented or decremented. Relative skew for the N channels is derived from the addresses of the first counter to overflow for each of the N channels.

Transparent synchronization of multiple channel data

Error correction for polynomial block codes is achieved without prior evaluation of power sum symmetric functions. The received word R (z) is reduced mod G (z), the generator of the code and a function F (z) of error locator polynomial W(z), errata values Y and code dependent functions f(x.sub.i) of the error positions x.sub.i given by ##EQU1## is decomposed into a rational polynomial function N (z)/W (z) for which deg (N (z) )&lt;deg ( W (z) )&lt;number of correctable errors. W (z) is the error locator polynomial, the roots of which are the errata locations X and Y, the correction to the received character is obtained from ##EQU2## evaluated at X.sub.i using non-erased check symbols of R (z). Correction is carried out in a crossbar switch structure which recalls a stored copy of R (z) and corrects bits as specified by (X.sub.i, Y.sub.i). Another embodiment interposes a matrix transform to transform the symbols of the received word so as to treat a selected set of symbols as erased checks and to present error location corrections directly to the crossbar. Only when changes occur in the pattern of errata is this error corrector apparatus required to operate and to redetermine the transform executed on incoming data R (z).

Error correction for algebraic block codes

To each bit time of a data block, there is associated a counter which is incremented or decremented in accord with the congruence or non-congruence of the c bit sequence associated with the respective counter (for example, the first bit of the c bit sequence). The counters are initialized to an optimum non-zero value and after receiving a number of blocks of data, each containing one sync symbol, the synchronization is determined from the relative content of the counters.

Method and apparatus for synchronization by coherent reinforcement

An improved method and apparatus for interleaving block codes exploits helical symmetry whereby correspondingly positioned code symbols of code words of length n interleaved to depth i, i&lt;n, are separated on the channel by .alpha.i+.beta. symbol intervals where 1+.gamma..gtoreq.i is averaged over the i correspondingly positioned symbols and .alpha.and .vertline..beta..vertline. are integers &gt;1. The requirement for synchrony is reduced to a period counted modulo n instead of mod (n.times.i). For the case i=n-1, the total interleaving delay is reduced to 2(n-1)n and phase dependence of burst error onset is minimized. The performance of the de-interleaver is enhanced through a pseudo fade detector implemented by creating erasures prior to decoding, at certain positions for codewords subsequent to confirmed error. Synchronization of interleaver and de-interleaver is accomplished in apparatus which inspects all c contiguous bit patterns corresponding to a c bit synch symbol. To each c contiguous bit pattern of the data stream there is associated a probability counter for incrementing when the synch pattern is detected and decremented otherwise. Maximum probability establishes synch.

Interleavers for digital communications

An encoder for Reed Solomon codes employs structure for producing interleaved code wherein redundancy bits are realized by a bit serial multiplicative procedure. Operations are accomplished with respect to the dual basis to the conventional polynomial representational basis as coefficients of successive powers of an element of a finite field. Code bits are generated and interleaved by a feedback shift register constructed from standard RAM chips. The structure is simplified by selection of a generator polynomial from a class which exhibits symmetry whereby the number of independent coefficients for representing the generator polynomial is halved.

Bit serial encoder

Errors are corrected in a cyclic encoded data stream, consisting of sequential groups of data bits and check bits, by means of a novel digital computer. The computer employs a stored program and is organized into three distinct substructures, each having an independent internal addressable memory and all capable of synchronous concurrent operation. An arithmetic unit substructure including a data memory implements finite field arithmetic operations upon received data. The arithmetic unit includes a Galois field manipulative subunit for producing finite field products and sums over the field GF(2.sup.5) from operands selected from three registers which derive data from the memory of the arithmetic unit, another register, or the result of a currently executed Galois field operation. The preferred embodiment is especially suitable for correcting data encoded in the Reed-Solomon (31,15) code. An address generator realizes address modification in the Galois field GF(2.sup.7), whereby consecutive addresses in data memory are characterized by a shift register sequence. The address generator includes a counter memory array and an equality test facility. Counter memory words of the address generator may selectably retain either the modified or non-modified address. A control unit substructure includes a control memory for storage and execution of the instruction sequence, branching logic for determining the transfer of control in response to logical functions of up to 16 logical variables, and select means and gating means for execution of instructions in all three substructures. Provision for data dependent arithmetic function selection, not employed for decoding the (31,15) Reed Solomon Code, permits the operation of the apparatus to yield solutions at high speed to simultaneous linear binary equations.

Growing community of inventors

Berkeley, CA, United States of America

Elwyn R Berlekamp