Title

Construction Of Fast Recovery Codes Using A New Optimal Importance Sampling Method

Keywords

Convolutional codes; Fast simulation; Importance sampling (IS); M-algorithm (MA); Markov systems; Sequential decoding

Abstract

In this correspondence, we introduce the problem of constructing good fast recovery convolutional codes. When the constraint lengths of the candidate codes are long (say more than 12), it is too computationally complex to perform the code search task. Fortunately, we can transform the code construction problem to a problem related to a transient Markov system. We then develop an optimal importance sampling (IS) method to fulfill the tasks. In this correspondence, we also prove several propositions for optimal IS. For Instance, we show analytically that the optimal IS method is unique. We prove that the optimal IS method must converge to the standard Monte Carlo (MC) simulation method when the sample path length approaches Infinity. This finding shows that it is not the size of the state space of the Markov system, but the sample path length, that limits the efficiency of the IS method. Based on insights from the optimal IS method, a sub-optimal IS method is then proposed to search for long fast recovery codes. The sub-optimal method can achieve a substantial speedup gain. After that, several numerical results are presented to study the efficiency of the IS methods and to justify the code search procedures. Finally, we give the code search results and the application of these codes.

Publication Date

11-1-2001

Publication Title

IEEE Transactions on Information Theory

Volume

47

Issue

7

Number of Pages

3006-3019

Document Type

Article

Personal Identifier

scopus

DOI Link

https://doi.org/10.1109/18.959280

Socpus ID

0035504621 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/0035504621

This document is currently not available here.

Share

COinS