Browse Prior Art Database

Family of Three Burst-Correcting Array Codes

IP.com Disclosure Number: IPCOM000035181D
Original Publication Date: 1989-Jun-01
Included in the Prior Art Database: 2005-Jan-28
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Related People

Blaum, M: AUTHOR [+2]

Abstract

Described herein is an array code for correcting three bursts of errors.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 2

Family of Three Burst-Correcting Array Codes

Described herein is an array code for correcting three bursts of errors.

Consider an n(1)xn(2) array code where n(2)/6n(1). n=n(1)n(2) is the length of the code and k=k1 k2 information bits are stored in the array, k1=n(1)-1 and k2=n(2)-2 [log2n(2)]-1. Information bits 0,1 ... k-1 are stored in k1(n(1)-1) rows of k2 bits each such that row i contains bits <i+(i-j)n(1)>n, 0&u&k1-1, 0&j&k2-1. (The notation <j>n is used to represent a unique integer i, 0&i&n, such that iXj(mod n) for given integers j and n, n>0).

Once the information bits are stored, 2[log2n(2)]+1 redundant bits in each row are obtained using a linear (BCH) encoder, thereby obtaining <i+(i-j)n(1)>n, k2&j&n(2)-1. The last row, i.e. row n(1)-1 is obtained by exclusively OR'ing the first n1-1 bits in each column. Once the encoding is completed, the bits are transmitted in natural order 0, l, into the channel.

Suppose bits a0 a1 ... an-1 are transmitted and bits a0 a1 ... an-1are received. The encoder will attempt to retrieve the transmitted bits and output the k information bits. If three or fewer bursts of length &n(1) have occurred, the decoding will be successful, i.e. the output of the decoder will coincide with the transmitted information bits.

The received data a0 a1 ... an-1 are sent to a vertical syndrome generator, a horizontal syndrome generator, a modified horizontal syndrome generator and a vertical syndrome and data updater.

The vertical syndrome is a vector v0 v1 ... vn(2)-1 in which each coordinate j, 0&j&n(2)-1 is the exclusive OR of the entries in column j.

The vertical syndrome is sent to the vertical syndrome processor and to the vertical syndrome and data updater. The vertical syndrome processor identifies the location j in which the first one after an error-free gap occurs. A gap of length l/1 is a set of locations <j+1>n(2), <j+2>n(2) ... <j+l>n(2) such that v<j+t>n(2)=0 for 1&t&l, v<j>n(2)=1 and v<j+e+1>n(2)=1.

A gap is error free if the corresponding columns of received data are error free. The way the vertical syndrome determines an error-free gap of length /n(1) is to find the gaps of length /n(1), number of which can be 1, 2, or 3. Let these gaps have length gk and let the segments in between the gaps have lk, once the lengths gk and lk are found, the error-free gap is found as follows: -- if there is only one gap of length /n(1), take it as the error-free gap; -- if there are two gaps of length /n(1), take the longest one as the gap; -- if there are three gaps of length /n(1), take any gap whose length gk satisfies (n(1)+1-lk-1) + (n(1)+1- lk)&gk .

Once the error-free gap of length l/n(1) has been identified, say at locations <k+1>n(2), <k+2>n(2) ... <k+l)n(2), the vertical syndrome processor produces as output location j=<k+l+1>n(2) which is sent to...