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

Cyclic Code Correction Device for Independent Errors

IP.com Disclosure Number: IPCOM000091848D
Original Publication Date: 1968-Jun-01
Included in the Prior Art Database: 2005-Mar-05
Document File: 3 page(s) / 31K

Publishing Venue

IBM

Related People

Juget, P: AUTHOR [+2]

Abstract

This error-correction device is applicable to a transmission system using cyclic codes characterized by the relation 2/m-1/ = n+1. In this expression m equals the number of information bits contained in one code vector and n equals the total number of bits in one code vector, that is, there are m information bits+(n -m) redundancy 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 52% of the total text.

Page 1 of 3

Cyclic Code Correction Device for Independent Errors

This error-correction device is applicable to a transmission system using cyclic codes characterized by the relation 2/m-1/ = n+1. In this expression m equals the number of information bits contained in one code vector and n equals the total number of bits in one code vector, that is, there are m information bits+(n -m) redundancy bits.

The code described is the 15/5 cyclic code which comprises words of 15 bits including 5 data bits and 10 control bits so that m=5 and n=15. Such code permits the correction of three errors independently located in each word.

On the transmission side, the coding system is of the standard systematical type. It carries out the logic division of information vector I (x) (5 bits), shifted 10 rows to the right, that is x/10/. I (x), by the polynomial generator of code g (x) of order 10. Coefficients of x are modulo-2 processed. The rest of this division gamma (x), of order 9, constitutes the 10 control bits. The emitted code vector is gamma (x) + x/10/ I (x). On the receiving side, the decoding problem resides in the recognition of the transmitted code vector, despite the presence of errors.

The 15/5 code comprises 32 code vectors since the information 5 bits can assume 32 values. These 32 code vectors are made up of a. the polynomial which generates code x/k/g (x) in

which k=4, since the degree of polynomial x/k/g (x) must be

equal to 14 in other words, equal to the degree of the code

vector, as well as the polynomial obtained by the 14

circular permutations of that generating polynomial,

(Image Omitted)

b. the complementary vector x/k//g (x) and of the 14 vectors

obtained by the

14 circular permutations of that complementary vector,

and

c. the vector nil and its complement.

In decoding, the emitted code vector is compared with each of the 32 code vectors to which it can belong. Since these 32 vectors are complementary two- by-two, only 16 comparison operations are thus necessary. The compare operation consists in adding, without carry, the code vector, or word received, to one of the 32 code vectors and then counting the number of 1's contained in the sum vector. Each 1 corresponds to a disparity between the received word and the code vector used or parity with a complementary code vector. The complement to 15 of the number of 1's gives a parity with the code vector itself.

Since the number of errors to correct is at the most equal to 3, the count obtained is therefore compared to the two thresholds, 12 for the comparison vector and 3 for its complement.

1

Page 2 of 3

If the number of 1's is between 3 and 12, a new comparison is made between the word received and another code vector or, in order to simplify the circuits, between the same code vector and the received word which is subjected to a one row looped shift, etc.

The drawing shows a 15/5 cyclic code decoder. The code vector, or word received, is stored in register B. Code vector x g (x) is it...