Browse Prior Art Database

Shortened Cyclic Code with Burst Error Detection and Synchronization Recovery Capability

IP.com Disclosure Number: IPCOM000080320D
Original Publication Date: 1973-Nov-01
Included in the Prior Art Database: 2005-Feb-27
Document File: 3 page(s) / 35K

Publishing Venue

IBM

Related People

Bahl, LR: AUTHOR [+2]

Abstract

Cyclic codes of shortened block lengths (e.g., 40 bits) which have good capability for correcting synchronization errors and detecting burst errors can be generated by unique polynomials, one example of which is described herein.

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

Page 1 of 3

Shortened Cyclic Code with Burst Error Detection and Synchronization Recovery Capability

Cyclic codes of shortened block lengths (e.g., 40 bits) which have good capability for correcting synchronization errors and detecting burst errors can be generated by unique polynomials, one example of which is described herein.

It is well known that cyclic coset codes can be used effectively for synchronization loss detection. Any (n,k) cyclic code can be made invulnerable to synchronization loss of up to n-k-1 positions, by adding a 1 to the first symbol of a code word or block.

However, if the code is shortened to a (n-upsilon,k-upsilon) code, the synchronization loss detection capability is reduced to n-k-upsilon-1. If the code block is shortened by n-k-1 or more bits, the code may have no synchronization loss detection capability.

There now is described a technique for constructing a large class of shortened codes with good synchronization loss detection capability. Let g(x) be the generator polynomial of a cyclic code having block length n. Assume that it is desired to shorten this length to n'. Let g(x) be factored into two parts, thus: g(1)(x) = g(1)(x).g(2)(x) Then, the following theorem can be proved:

If g(1)(x)|x/n'+2/ -1, then the shortened code generated by g(x) of block length n' can detect synchronization loss of up to r(1)-upsilon-1 positions, where r(1) is the degree of g(1)(x). The most interesting case is where upsilon=0, so that synchronization loss of up to r(1)-1 positions is detectable.

As an example of how the above results may be used, consider the design of a code whose requirements are as follows: Block length n' = 40 Information bits/block = 32 Sync loss detection capability = 3 Error detection capability: should detect 2 bursts of length 2 to 3 in a code word.

First attempt to find a code having natural block length n=40. Now (x/40/ -1) = [(x-1)(x/4/+x/3/+x/2/+x+1)]/8/, and every g(x) of degree 8 such that g(x)|x/40/ -1 leads to a code with minimum distance 2, which implies that the required error detection capability is not fulfilled. Therefore, now look for a suitable shortened code.

To have a synchronization loss detection capability of 3 guaranteed by the above theorem (with upsilon=0), choose a g(1)(x) of degree 4 such that g(1)(x) |x/40/ -1. The only possibilities for g(1)(x) are (x/4/-1) or (x/4/+x/3/+x/2/+x+1). Now g/2/(x) must be chosen in such a way that the code generated by g(x) = g(1)(x).g (x) has natural block length n>/-40. If g/1/(x) = x/4/+x/3/+x/2/+x+1, no such g(2)(x)...