International Business Machines Corporation

Miguel M Blaum

Jehoshua Bruck

Jaishankar Moothedath Menon

Glenn T Sincerbox

Paul H Siegel

Hsieh T Hao

Alexander Vardy

Howard Thomas Olnowich

James T Brady

Norman Ken Ouchi

Constantin Michael Melas

Richard L Mattson

Ron M Roth

Henricus C Van Tilborg

An error checking method and apparatus for appending a variable number of redundancy coding information at the end of each data message or packet transmitted over a multi-stage network for the purpose of protecting the data by using an error detecting code. The amount of additional redundancy coding information implemented is variable and increases with the size of the data message or packet to provide a consistent level of protection.

Variable cyclic redundancy coding method and apparatus for use in a

A modulator apparatus for modulating arrays of input data V.sub.in to be stored in a holographic recording medium is disclosed wherein the final output data array V.sub.out has frequent transitions from light to dark and from dark to light in either dimension across the data page and has the total amount of illuminated regions throughout the entire data page held constant. These two constraints are achieved by a first set of control arrays obtained from two fixed sets of m.times.n binary arrays {A.sub.0, A.sub.1, . . . , A.sub.n } and {B.sub.0, B.sub.1, . . . , B.sub.m } which in turn are obtained from fixed sets of binary control vectors {a.sub.0, a.sub.1, . . . , a.sub.n }, {b.sub.0, b.sub.1, . . . , b.sub.m }, respectively. The control vectors a.sub.0, a.sub.1, . . . , a.sub.n are any n+1 fixed elements of the inverse mapping, .phi..sup.-1 (C.sub.1), of the (t-2) error-correcting code C.sub.1 of length m. The control vectors b.sub.0, b.sub.1, . . . , b.sub.m are any m+1 fixed elements of the inverse mapping, .phi..sup.-1 (C.sub.2), of the (t-2) error correcting code C.sub.2 of length n. The first constraint is achieved by V'.sub.in =V.sub.in .sym.(A.sym.B). In order to balance the modulated array, a second set of control arrays {W.sub.0, W.sub.1, W.sub.2. . . , W.sub.mn-1 } is obtained from the set of control vectors {w.sub.0, w.sub.1, w.sub.2. . . , w.sub.mn-1 }. The second constraint is achieved by complementing the bits of the input binary array V'.sub.in in a horizontal readout order terminating after the first i bits. The final modulated output array V.sub.out =V'.sub.in .sym.W simultaneously satisfies both constraints.

Method and apparatus for modulation of multi-dimensional data in

The data contents of up to two concurrently failed or erased DASDs can be reconstituted where the data is distributed across M DASDs as an (M-1)*M block array and where (1) the (M-1)st DASD contains the simple parity taken over each of the array diagonals in diagonal major order in the same mode (odd/even) as that exhibited by the major diagonal of the array and (2) where the M-th DASD contains the simple even parity over each of the rows in row major order. Relatedly, short write updates require fewer operations for data blocks located off the major data array diagonal.

Method and means for encoding and rebuilding the data contents of up to

A modulator apparatus for modulating arrays of input data V.sub.in to be stored in a holographic recording medium is disclosed wherein the final output data array V.sub.out has frequent transitions from light to dark and from dark to light in either dimension across the data page and has the total amount of illuminated regions throughout the entire data page held constant. These two constraints are achieved by a first set of control arrays obtained from two fixed sets of m.times.n binary arrays {A.sub.0, A.sub.1, . . . , A.sub.n } and {B.sub.0, B.sub.1, . . . , B.sub.m } which in turn are obtained from fixed sets of binary control vectors {a.sub.0, a.sub.0, a.sub.1, . . . , a.sub.n }, {b.sub.0, b.sub.1, . . . , b.sub.m }, respectively. The control vectors a.sub.0, a.sub.1, . . . , a.sub.n any n+1 fixed elements of the inverse mapping, .phi. .sup.1 (C.sub.1), of the (t-2) error-correcting code C.sub.1 of length m. The control vectors b.sub.0, b.sub.1, . . . , b.sub.m are any m+1 fixed elements of the inverse mapping, .phi. .sup.1 (C.sub.2), of the (t-s) error-correcting code C.sub.2 of length n. The first constraint is achieved by V'.sub.in =V.sub.in .sym.(A.sym.B). In order to balance the modulated array, a second set of control arrays {W.sub.0, W.sub.1, W.sub.2, . . . , W.sub.1, W.sub.2, . . . , W.sub.mn-1 } is obtained from the set of control vectors {W.sub.0, W.sub.1, W.sub.2, . . . , W.sub.mn-1 }. The second constraint is achieved by complementing the bits of the input binary array V'.sub.in in a horizontal readout order terminating after the first i bits. The final modulated output array V.sub.out =V'.sub.in .sym.W simultaneously satisfies both constraints.

A method is disclosed for recovery from synchronization errors caused by deletions and/or insertions of symbols in the presence of errors that alter the symbols in any code constrained binary record. The method initially divides the sequence of data into equal size blocks before appending a binary sync sequence at the end of each block not encountered in the block. Then, the blocks are resynchronized by first determining the size of any symbol insertions and/or deletions that have occurred. Then, scanning for the sync sequence starting at the presumed end of the data field of the current block so as to determine the offset of the sync sequence with respect to that specific location. After this location of the insertions and/or deletions has been determined, a corresponding number of symbols can be added or deleted from the middle of the block according to the offset determined by the present method.

Method for bit resynchronization of code-constrained sequences

A method and apparatus for encoding and decoding a (t.sub.1,t.sub.2)-skew-tolerant (ST) (t.sub.1 +s.sub.1,t.sub.2 +s.sub.2)-skew-detecting (SD) code, and for correcting and detecting skewed transitions in a parallel asynchronous communication system without acknowledgement, where t.sub.1, t.sub.2, s.sub.1, and s.sub.2 are selectable nonnegative integers. Even though transitions sent at the same time in parallel channels may arrive at different times, a limited degree of variation in transmission speeds is permitted between channels. Assume t.sub.1 is the maximum correctable number and t.sub.1 +s.sub.1 the maximum detectable number of transitions that can be missing from a first transmitted codeword when the first transition arrives from a second transmitted codeword, and t.sub.2 is the maximum correctable number and t.sub.2 +s.sub.2 the maximum detectable number of transitions from the second codeword that can arrive before the last transition of the first codeword arrives. Errors will be corrected and transmissions will be continuous as long as the values of both t.sub.1 and t.sub.2, as preselected by the user, are not exceeded. If either t.sub.1 or t.sub.2 is exceeded, a desired control operation will generally be initiated. If the value of either t.sub.1 or t.sub.2 is exceeded, but the values of both t.sub.1 +s.sub.1 and t.sub.2 +s.sub.2 are not, then the control operation will always be successful in detecting skew.

Coding method for correction and detection of skewed transitions in

A method and means for coding an (M-1).times.M data array written onto an array of M synchronous recording paths and for rebuilding and writing onto spare recording path capacity when up to a preselected number R of array DASDs fail, or one DASD becomes erroneous and up to R-2 fail. Data is mapped into the parallel paths using an (M-1).times.M data and parity block array as the storage model where M is a prime number and each block extent is uniform and at least one bit in length. The (M-1).times.M data and parity block array is encoded to include zero XOR sums along a traverses of slopes 0, 1, 2, . . . , P-1, extended cyclically over said data array. Rebuilding data and parity blocks is occasioned upon unavailability of no more than R less than or equal to P recording path failures, or one recording path in error and up to R-2 recording path failures. This includes calculating XOR-sums along the traversed paths of P-1 slopes, cyclic and linear shifts and XOR operations, recovering the unavailable DASDs by means of iterative solution of a set of recursions, and finally writing the rebuilt array back to onto M recording paths inclusive of any spare paths.

Method and means for coding and rebuilding that data contents of

B-Adjacent coding is used to correct up to two DASDs in error in an array of N data DASDs and two redundant DASDs. When two of the data DASDs fail, their data can be recreated as a function of a pair of syndromes constituting up to two Boolean equations in two unknowns. Prestoring of the matrices of the powers of the polynomial terms of the code primitive together with pipeline processing operate to expedite data recovery and balance the write operations load on the DASDs across the array. Recovery from the failure of a data and a redundant DASD involves resolving one linear Boolean equation with one unknown.

Method and means for b-adjacent coding and rebuilding data from up to

Decoding power is enhanced by (1) flagging only those codewords where the ECC capability has been exceeded; (2) permitting codewords to be of any byte length (n) and codeword depth (.lambda.) subject only to the requirement that n and .lambda. be relatively prime; and (3) interleaving encoded bytes of successive codewords diagonally in a single continuous sequence to form an array with a toroidal topology so that all burst errors will be continuous from codeword to codeword, irrespective of where they occur in the array. These attributes assure that there will never be a problem with burst errors affecting.ltoreq..lambda. rows because there is no 'last row' and 'first row'.

Enhanced decoding of interleaved error correcting codes

An unordered error correcting code is constructed by an encoding method and apparatus that accepts k bits of information and is capable of providing unordered ECC codewords. All pairs of these codewords are at least a distance d apart, where d.gtoreq.(2t+1) and t is the maximum number of errors correctable by the code. The k bits of information are encoded with an ECC encoding algorithm to produce ECC codewords that are at least distance d apart. The least number of tail bits required to produce the unordered ECC codewords is appended to each of the ECC codewords. The tail bits for each codeword are constructed by dividing its weight by d for determining the integer part of the resulting quotient, generating a binary representation of the value of its integer part, and complementing said binary representation. A noisy received version of the ECC codeword with tail bits truncated is decoded and a preselected error correcting algorithm is applied to correct t.sub.1 actual errors and produce a decoded ECC codeword. Tail bits corresponding to the decoded ECC codeword are generated and compared with segregated tail bits for the noisy received ECC codeword for determining the number t.sub.2 of errors actually detected. The k information bits derived from the decoded ECC codeword are outputted when (t.sub.1 +t.sub.2).ltoreq.t.

Method and apparatus for encoding and decoding unordered error

An algorithm for a (t.sub.1, t.sub.2)-tolerant code, and a method and apparatus for decoding same, for tolerating and detecting skewed transitions in a parallel asynchronous communication system without acknowledgement. Transitions sent at the same time in a parallel channel may arrive at different times, but the algorithm permits a limited degree of variation in transmission speeds between channels. Errors will be corrected and transmissions will be continuous as long as the values of t.sub.1 or t.sub.2 for the algorithm, as preselected by the user, are not exceeded. If they are exceeded, a desired control operation will generally be initiated. t.sub.1 is the maximum number of transmissions that may be missing from a first transmitted codeword when a transmission arrives from a second transmitted codeword, and t.sub.2 is the maximum number of transitions from the second codeword that may arrive before all transitions of the first codeword arrive.

Coding method for skewed transition correction in parallel asynchronous

An algorithm for a (t.sub.1,t.sub.2)-detecting code, and a method and apparatus for decoding same, for detecting skewed transitions in a parallel asynchronous communication system without acknowledgement. Transitions sent at the same time in a parallel channel may arrive at different times, but the algorithm permits a limited degree of variation in transmission speeds between channels. A desired control operation will be initiated whenever a skewed transition occurs. The code will detect up to t.sub.1 or t.sub.2 skewed transitions. The values of t.sub.1 or t.sub.2 for the algorithm are preselected by the user. t.sub.1 is the maximum number of transitions that may be missing from a first transmitted codeword when a transition arrives from a second transmitted codeword, and t.sub.2 is the maximum number of transitions from the second codeword that may arrive before all transitions of the first codeword arrive.

Coding method for skewed transition detection in parallel asynchronous

A method and means for encoding data written onto an array of M synchronous DASDs and for rebuilding onto spare DASD array capacity when up to two array DASD fail. Data is mapped into the DASD array using an (M-1)*M data array as the storage model where M is a prime number. Pairs of simple parities are recursively encoded over data in respective diagonal major and intersecting row major order array directions. The encoding traverse covering a topologically cylindrical path. Rebuilding data upon unavailability of no more than two DASDs merely requires accessing the data array and repeating the encoding step where the diagonals are oppositely sloped and writing the rebuilt array back to onto M DASDs inclusive of the spare capacity.

Method and means for encoding and rebuilding data contents of up to two

A method for implementing error-correcting codes for disks, wherein the statistics of error vary according to the radius of the location being accessed. A Reed-Solomon code is selected having data bytes and redundant bytes and an error-correcting capability sufficient to protect against an anticipated worst case or errors. The number of redundant bytes in that code, and thereby the number of correctable errors, is progressively reduced in respective concentric areas of the disk according to the statistics of error for such areas, for thereby progressively reducing the number of correctable errors as the need for error correction capability decreases. For multiband recording, the areas are concentric bands in each of which data is recorded at a clock frequency substantially proportional to its inner diameter; and in such case, the number of redundant bytes is reduced progressively in each successive band toward the innermost band. For conventional recording, the areas are concentric tracks recorded at substantially the same frequency; and in such case, the number of redundant bytes is reduced toward the outermost concentric area. This method may also be used to increase correction capability periodically when capability decreases, due for example to corrosion of a write-once optical disk.

Growing community of inventors

San Jose, CA, United States of America

Miguel M Blaum