Browse Prior Art Database

Character Cyclic Codes

IP.com Disclosure Number: IPCOM000095099D
Original Publication Date: 1965-Sep-01
Included in the Prior Art Database: 2005-Mar-07
Document File: 3 page(s) / 49K

Publishing Venue

IBM

Related People

Rogers, WF: AUTHOR

Abstract

Error detecting cyclic codes are developed for data transmission. The codes can be encoded and decoded by a shift register and also by computer program without the necessity for external hardware.

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 49% of the total text.

Page 1 of 3

Character Cyclic Codes

Error detecting cyclic codes are developed for data transmission. The codes can be encoded and decoded by a shift register and also by computer program without the necessity for external hardware.

The number of check bits, for example, is fourteen. The number of information bits is about 7, 000 per word. The data word is a sequence of characters with seven information bits per character with start and stop bits ignored for code analysis.

Cyclic code words which are acceptable for transmission are those whose representative polynomials are in the residue class (0) modulo G(X), the generator polynomial. Polynomials in the (0) residue class are all those which are divisible by C(X) with zero remainder and thus are all the multiples of G(X). Division of polynomials is performed during encoding and decoding to determine the remainder R(X). A particular degree of the polynomial term corresponds to a unit bit in time on the line. The highest degree term of the polynomial occurs first.

Circuit a encodes a bit cyclic check character when G(X) = X/14/+X/13/+X/5/ +X/3/+X/2/+ 1. Switches S1 and S2, and Or 1 accomplish the gating necessary. Switch S1 is closed and switch S2 opened for calculation of the remainder polynomial R(X), while P(X), the information k bit sequence, is being sent on the line. After the last bit of P(X) has entered the register, switch S1 is opened and switch S2 is closed to shift the remainder onto the line to complete the encoded word.

The only class of bit cyclic codes which can be coded by simple shift register circuitry and simple character manipulation instructions is defined as: G(X)=1+g(n)X/n/+g(2n)X/2n+/.......... In the equation n is the number of bits per
character and the polynomial coefficients are taken from the field of two elements. The only character manipulation instruction needed by the computer is exclusive-or character to register. Two specific codes from this class, X/14/+1, and X/14/ +X/7/ + 1, are useful for encoding information and checking the resulting code polynomial in the reverse direction.

Assume that P(X) is divided into 7-bit characters. Circuit b divides P(X) by G(X) = X+ 1, where the coefficients of the polynomials are taken from the field mod X7 and each 7-bit character represents a coefficient. Thus, to perform this division and find the resulting remainder R(X), it is necessary to subtract the first character of ' P(X) from the second character resulting in a sub-remainder. This sub-remainder is subtracted from the third character or P(X) yielding another sub-remainder which is subtracted from the fourth character, and so forth until the final remainder R(X) results. The first bit in time of each character of P(X) is the lowest order bit. In circuit b in order to subtract Q(X) from P(X) one character at a time, Q(X) is complemented, i. e., inverted, to form Q(X). Then Q(X) is added to P(X). To add, it is required to generate the carry C(X). This has the function...