Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Fast Decoding Method for Error Correcting Code

IP.com Disclosure Number: IPCOM000078006D
Original Publication Date: 1972-Oct-01
Included in the Prior Art Database: 2005-Feb-25
Document File: 4 page(s) / 48K

Publishing Venue

IBM

Related People

Petersen, JE: AUTHOR

Abstract

Described is an improved decoding scheme for a type of error-correction code in United States Patent 3,622,954. In one version of the error-correction code seen in Fig. 1. two k-bit wide check groups are formed for each record transmitted or received. The pattern group is created by the serial exclusive OR of each data bit into a k-bit cyclic shift register P via exclusive OR 1. while the displacement group is formed by the parallel exclusive OR, gated by each data bit, of an m'-bit wide binary count register, C, into another k-bit-wide cyclic shift register D, C being updated every j' data bits.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 48% of the total text.

Page 1 of 4

Fast Decoding Method for Error Correcting Code

Described is an improved decoding scheme for a type of error-correction code in United States Patent 3,622,954. In one version of the error-correction code seen in Fig. 1. two k-bit wide check groups are formed for each record transmitted or received. The pattern group is created by the serial exclusive OR of each data bit into a k-bit cyclic shift register P via exclusive OR 1. while the displacement group is formed by the parallel exclusive OR, gated by each data bit, of an m'-bit wide binary count register, C, into another k-bit-wide cyclic shift register D, C being updated every j' data bits.

During transmission, each record is followed by the check group pair generated from its data. When received, each record is used to make another pair which is then exclusively OR'ed with the transmitted pair, to produce the pattern and displacement error syndromes for the record. These syndromes reflect the occurrence of errors between transmission and reception of the record, and under certain conditions may be used to correct these errors.

The two k-bit cyclic shift registers, P and D, respectively, shift in the same direction as those used to generate the check groups, and in fact can be the same registers used to generate the check pair for the received record. Let P(i) represent the bit within P affected by the (i)th data bit, and let D(i) be that bit of D affected by gating the counter bit of weight 2/t/ by the (i-t)th data bit. This latter definition implies that D must shift higher weighted entires toward lower. Note that P(i)=P(i') and D(i)=D(i') when i and i' differ by a multiple of k.

Assuming that the error is confined to bits i, i+1,..., i+b-1 of the n-bit data record, with bit i being the first bit in error, then i can be uniquely determined by the method described below, provided that (a) j >/- b-1, where j=(2 )j' for some r > and j~ divides k, (b) k >/- 2b-1, (c) k >/- b+m-1, where m=(m'-r), and (d) n </- (2/m/)j. These conditions guarantee that

(a) the data may be grouped in words of j bits, each with the error burst occupying at most two such words, and the effects of the r low-order bits of C can be removed so that each word may be associated with a single counter value,

(b) the first bit of the error can be uniquely located up to a multiple of k (or j) bits,

(c) no effective bits of C gated into D by error bits, will overlap a bit gated from the effective low-order bit of C by an earlier error bit, and

(d) no two words have the same counter value, i.e., if L(i') represents the effective counter value when bit i' is processed, then L(i')= L(i'') if and only if bits i' and i'' are in the same word.

Prior to decoding, the effect of the low-order r bits of C must be eliminated unless r=o.. This may be done in a number of ways, the most common being either to update C only every j bits or not to use its low-order bits when generating the displacement groups. If the low-order bi...