Lara Dolecek and Venkat Anantharam

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2006-44

April 27, 2006

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-44.pdf

We analyze the performance of a Reed-Muller RM(1,m) code over a channel that, in addition to substitution errors, permits either the repetition of a single bit or the deletion of a single bit; the latter feature is used to model synchronization errors. We first analyze the runlength structure of this code. We enumerate all pairs of codewords that can result in the same sequence after the deletion of a single bit, and propose a simple way to prune the code by dropping one information bit such that the resulting linear subcode has good post-deletion and post-repetition minimum distance. A bounded distance decoding algorithm is provided for the use of this pruned code over the channel. This algorithm has the same order of complexity as the usual fast Hadamard transform based decoder for the RM(1,m) code.

---

BibTeX citation:

@techreport{Dolecek:EECS-2006-44,
    Author= {Dolecek, Lara and Anantharam, Venkat},
    Title= {Using Reed-Muller RM(1,m) Codes over Channels with Synchronization and Substitution Errors},
    Year= {2006},
    Month= {Apr},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-44.html},
    Number= {UCB/EECS-2006-44},
    Abstract= {We analyze the performance of a Reed-Muller RM(1,m) code over a channel that, in addition to substitution errors, permits either the repetition of a single bit or the deletion of a single bit; the latter feature is used to model synchronization errors. We first analyze the runlength structure of this code. We enumerate all pairs of codewords that can result in the same sequence after
the deletion of a single bit, and propose a simple way to prune the code by dropping one information bit such that the resulting linear subcode has good post-deletion and post-repetition minimum distance. A bounded distance decoding algorithm is provided for the use of this pruned code over the channel. This algorithm has the same order of complexity as the usual fast Hadamard transform based decoder for the RM(1,m) code.},
}

EndNote citation:

%0 Report
%A Dolecek, Lara 
%A Anantharam, Venkat 
%T Using Reed-Muller RM(1,m) Codes over Channels with Synchronization and Substitution Errors
%I EECS Department, University of California, Berkeley
%D 2006
%8 April 27
%@ UCB/EECS-2006-44
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-44.html
%F Dolecek:EECS-2006-44