Near-Capacity Variable-Length Coding: Regular and EXIT-Chart-Aided Irregular Designs

Appendix A

VLC Construction Algorithms

A.1 First RVLC Construction Algorithm

We now introduce the MRG-based algorithm proposed in [21] by slightly paraphrasing it as follows. Continuing the list of definitions in Section 3.3.1, we add:

Definition 12 (Minimum Repetition Gap (MRG) [21]) A codeword c having k bits is represented as c₁c₂ ... c_k. We form a new bit pattern b by concatenating c with a k-bit pattern x yielding the pattern b = cx. Every bit in x can be viewed as ‘0’ or ‘1’ in the following calculation. The minimum repetition gap g of c may be defined as the minimal-length interval that can be created for which it is valid that all the bits in b are repeated every g bits, ie. appear to be repeated every g bits. This may be formulated mathematically as:

For example, given a codeword c = 010, we have k = 3. The resultant 2k-bit long concatenated pattern is formulated as b = 010x₁x₂x₃. We can opt, for example, for setting x = 101, resulting in b₁ = b₃ = b₅ (i.e. x₂) = 0 and b₂ = b₄(x₁) = b₆(x₃) = 1. Therefore, by observing the resultant six-bit pattern of 010101 we infer that the two-bit pattern of 01 repeats itself. Hence we conclude that g is equal to 2 in this case. Alternatively, we may opt for x = 010, in which case we have a six-bit pattern of 010010 emerging, and hence we infer that the three-bit pattern of 010 repeats itself. Therefore we conclude that g is equal to ...