Browse Prior Art Database

Resynchronizing (d,k) Constrained Sequences in the Presence of Insertions and Deletions

IP.com Disclosure Number: IPCOM000110582D
Original Publication Date: 1992-Dec-01
Included in the Prior Art Database: 2005-Mar-25
Document File: 1 page(s) / 53K

Publishing Venue

IBM

Related People

Blaum, M: AUTHOR [+4]

Abstract

Given a (d,k)-constrained sequence, a loss of synchronization may occur by insertion or deletion of a 0 or a 1. That event is catastrophic, i.e., it will cause an unlimited number of errors once synchronization is lost. Disclosed is a method that allows for identification of insertions and/or deletions in a given block with high probability, permitting quick synch recovery.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 64% of the total text.

Resynchronizing (d,k) Constrained Sequences in the Presence of Insertions and Deletions

       Given a (d,k)-constrained sequence, a loss of
synchronization may occur by insertion or deletion of a 0 or a 1.
That event is catastrophic, i.e., it will cause an unlimited number
of errors once synchronization is lost.  Disclosed is a method that
allows for identification of insertions and/or deletions in a given
block with high probability, permitting quick synch recovery.

      Consider (1,7) sequences (the method can be generalized to any
(d,k) sequence).  We make the following 1-1 mapping between a (1,7)
sequence and symbols in Z7, the set of integers modulo 7: to each run
of 0's, we associate the number of zeros minus one.

      If we denote by L the length of the binary string, by l the
length of the 7-ary string and by S the sum of the symbols in the
7-ary string, these three parameters are related by L=S+2l.  At the
7-ary level, we encode the information using an (n,n-2) block code,
where n>6.  The first and the last symbols in a block are redundant,
while the middle n-2 symbols carry the information.  We require that
in each block, the sum of the symbols modulo 7 is 0.  The last symbol
in a block and the first symbol in the next block are chosen in such
a way that their sum is equal to 6.  Thus, we insert 10 binary
symbols between blocks in the binary sequence.

      At the receiving end, if we receive the 7-ary sequence b0,b1,
b2,..., and erro...