Browse Prior Art Database

Cyclic Decoder for Transposition Error Correction

IP.com Disclosure Number: IPCOM000090778D
Original Publication Date: 1969-Jul-01
Included in the Prior Art Database: 2005-Mar-05
Document File: 2 page(s) / 38K

Publishing Venue

IBM

Related People

Lum, VY: AUTHOR [+2]

Abstract

An alphanumeric keyboard or dial-in terminal, when utilized by an operator, is subjected to occasional errors caused by the operator. In particular, a common error is the transposition of a pair of adjacent symbols. To protect certain important data, such as ID numbers, from such errors, error-control codes can be used. This method corrects a single transposition error by a special type cf cyclic code.

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

Page 1 of 2

Cyclic Decoder for Transposition Error Correction

An alphanumeric keyboard or dial-in terminal, when utilized by an operator, is subjected to occasional errors caused by the operator. In particular, a common error is the transposition of a pair of adjacent symbols. To protect certain important data, such as ID numbers, from such errors, error-control codes can be used. This method corrects a single transposition error by a special type cf cyclic code.

Assume that the symbols of transmitted and received sequences are identified as elements of a finite field GF(q). A cyclic code generated by the generator polynomial g(x) of degree r consists of polynomials of degree no more than n-1, i.e., n-tuples, which are multiples of g(x). The code length n is the smallest integer such that g(x) divides X/n/-1. As an example, a full-length Hamming code with a generator polynomial g(x) which does not contain (x-1) as a factor is chosen. This is a single error-correcting code of length (q/r/-1)/(q-1) but is used for single transposition error correction.

It can be shown that x-1 identical to cx/b/ module g(x) for a certain unique c in GF(q) and a unique positive integer b </-n. It follows that x/n-b/ over c identical to 1 over x-1 mod g (x).

Since a transposition of adjacent symbols is equivalent to a pair of additive errors of opposite signs at the positions transposed, the syndrome corresponding to the transposition errors can be written as S(x) identical to e(i)(x-1)x/i/ mod...