Almost Sure Convergence of Relative Frequency of Occurrence of Burst Errors on Channels with Memory

Mitsuru HAMADA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E82-A   No.10   pp.2022-2033
Publication Date: 1999/10/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Information Theory and Its Applications)
Category: Coding Theory
burst-error-correcting code,  burst metric (weight),  Markov chain,  law of large numbers,  swept covering,  

Full Text: PDF(452KB)>>
Buy this Article

Motivated by intention to evaluate asymptotically multiple-burst-error-correcting codes on channels with memory, we will derive the following fact. Let {Zi } be a hidden Markov process, i. e. , a functional of a Markov chain with a finite state space, and Wb(Z1Z2Zn) denote the number of burst errors that appear in Z1Z2Zn, where the number of burst errors is counted using Gabidulin's burst metric , 1971. As the main result, we will prove the almost sure convergence of relative burst weight Wb(Z1Z2Zn)/n, i. e. , the relative frequency of occurrence of burst errors, for a broad class of functionals { Zi } of finite Markov chains. Functionals of Markov chains are often adopted as models of the noises on channels, especially on burst-noise channels, the most famous model of which is probably the Gilbert channel proposed in 1960. Those channel models described with Markov chains are called channels with memory (including channels with zero-memory, i. e. , memoryless ones). This work's achievement enables us to extend Gilbert's code performance evaluation in 1952, a landmark that offered the well-known Gilbert bound, discussed its relationship to the (memoryless) binary symmetric channel, and has been serving as a guide for the-Hamming-metric-based design of error-correcting codes, to the case of the-burst-metric-based codes (burst-error-correcting codes) and discrete channels with or without memory.