betaFeedback

WorksComputer Science

Error-correcting codes without parity-check bits

Abstract

We are developing a new approach to the problem of error correction in communication channels, in which the input sequence is transformed in such a way that the interdependence of symbols increases significantly. Then, after the sequence is transmitted over the channel, this property is used for error correction, so that the residual error rate is significantly reduced. A natural example of its application is the transmission of binary sequences whose entropy (per symbol) is less than one, since in this case the length of the transmitted sequence remains constant during encoding and decoding. An algorithm has been developed to implement the maximum likelihood method, in which the encoding and decoding times are linear. This algorithm was used to experimentally investigate its effectiveness on popular channel models, and it was found that there are certain sets of parameters for which the proposed method is quite effective.

Introduction

Since the publication of Claude Shannon’s famous article [1], the problem of efficient data transmission over noisy channels has occupied a central place in information theory. Hundreds of articles are published annually on various error correction methods, and various monographs, such as [2], [3], are devoted to this topic.

Many error-correcting codes studied in theory and used in practice are based on adding redundant symbols (usually parity bits) to the transmitted message. This class of methods includes block codes [2], [4], [5], convolutional codes [6], BCH codes [7], low-density parity-check codes [8], hash-function-based codes [9], and many others.

Another popular approach to transmission through a noisy channel is a so-called joint source-channel coding (JSCC) (see for review [10], [11]). In particular, this approach considers codes in which data redundancy is used to correct errors in noisy channels.

It is worth noting that when it is necessary to transmit low-entropy data over a noisy channel, it seems quite natural to first compress the message and then apply error-correcting coding. In the next section, we will outline this approach and show that problems related to loss of synchronization may arise when decoding the received sequence. Thus, it turns out that in a number of situations, it is better to omit the data compression step and look for other methods of joint source-channel coding.

In this article, we propose the following method of joint source-channel coding. The transmitted sequence is transformed in such a way that the interdependence of the symbols increases significantly, and the transformed sequences themselves follow a uniform distribution. Then, after the sequence is transmitted over the channel, these properties are used for error correction, which allows for a significant reduction in the residual error rate. Of course, this is possible only if the entropy of the transmitted binary sequences (per symbol) is less than one—that is, if the source has redundancy.

It is important to note that the encoding and decoding times in the proposed method are linear (i.e., the rate is constant); however, the required memory capacity can be quite large. So, taking into account that the encoding and decoding rates remain constant, it can be said that the method allows for a reduction in the error rate “at no cost.”

The transformation of the sequence is based on so-called two-faced processes (see [15] for definitions). After the transformed sequence is transmitted over the channel, the maximum likelihood method is used to estimate the transmitted sequence. An algorithm has been developed to implement the maximum likelihood method, in which the decoding time is linear. This algorithm was used to experimentally investigate its effectiveness on popular channel models, and it was found that there are certain sets of parameters for which the proposed method is quite effective.

The rest of the paper covers the following. The next section contains preliminary information and background details on “two-faced processes.” The subsequent sections describe the encoder and decoder, respectively. This is followed by the experimental results and a discussion of possible generalizations. The concluding section presents a brief summary.

Preliminaries

Some error-correcting codes for low-entropy sources

As Shannon noted in [1], it is quite natural to use the redundancy in transmitted data to correct errors that occur when the data is transmitted over a channel subject to noise. As we mentioned earlier, there are a number of studies in which this natural idea has been applied to various “source–channel” models. Among these works, it is worth noting [12], in which the author examines Markov sources with high redundancy and a discrete memoryless channel. He describes a method in which the source’s redundancy is used to combat errors in the channel. The idea of using data redundancy to correct channel errors was applied by a number of other authors in the 1990s [13], [14] and is currently being developed within the JSCC.

A schematic overview of the “compression first, then error correction” method

The proposed method can be applied when the entropy of a binary information source is less than one (per symbol). Therefore, we will briefly mention other options for transmitting data. with low entropy.

At first glance, it seems natural to first use a traditional lossless data compression method and then apply an error-correcting code. The receiver first performs error-correcting decoding and then “unpacks” the resulting sequence. However, this raises a “hidden” problem known as “error propagation” (or “loss of synchronization,” or “synchronization catastrophe”). The essence of the problem is this: when using lossless data compression methods, it is necessary to use codewords of varying lengths (otherwise, lossless compression is impossible!). However, using codewords of different lengths can lead to a loss of synchronization: in other words, even a single error remaining after the error correction stage can trigger a whole cascade of errors during decompression due to the loss of synchronization.

Consider, for example, an information source that generates the sequence x=x1…xnx=x_1\ldots x_n (n≥1n\geq1). Suppose we use a noisy channel and an error-correcting code with a bit error rate (BER) =α>0=\alpha>0 (i.e., when this code is applied to xx, the average number of corrupted symbols is nαn\alpha). If the original sequence was losslessly compressed into y=y1…ymy=y_1\ldots y_m and the same error-correcting code with the same BER =α=\alpha was applied to it, then after decompression the resulting BER will be proportional to nαn\alpha due to the error propagation effect. Consequently, a more robust error-correcting code must be used, which means a larger number of parity bits and increases the decoding time. This, in turn, can reduce data compression efficiency and increase encoding and decoding times.

The main tool of the proposed method: two-faced processes

In the main part of the article, we will consider information sources that generate letters from the alphabet {0,1}\{0,1\} and, in particular, a Bernoulli source B(p)B(p) that generates letters with probabilities P(0)=pP(0)=p, P(1)=qP(1)=q (=1−p=1-p), p≥1/2p\geq1/2.

The proposed code will be based on so-called two-faced processes, which are Markov chains of order (or memory) ss, s≥1s\geq1. This means that for the generated sequence …x−1x0x1…\ldots x_{-1}x_0x_1\ldots, the probability P(xi+1)P(x_{i+1}) depends on the ss preceding symbols, i.e., the probability $P(x_{i+1}=\alpha\mid …x−1x0x1…xix_{-1}x_0x_1\ldots x_i) is equal to P(xi+1=α∣xi−s+1…xi)P(x_{i+1}=\alpha\mid x_{i-s+1}\ldots x_i), where α∈{0,1}\alpha\in\{0,1\}. We will describe those chains by the following transition probability matrices:

\begin{array}{c|cc} & \multicolumn{2}{c}{\text{probability of zero}}\\ s=1:\quad& p & q\\ \text{after} & 0 & 1 \tag*{(1)} \end{array}

This means that Pr⁡{xi+1=0∣xi=0}=p\operatorname{Pr}\{x_{i+1}=0\mid x_i=0\}=p, Pr⁡{xi+1=0∣xi=1}=q\operatorname{Pr}\{x_{i+1}=0\mid x_i=1\}=q and, of course, Pr⁡{xi+1=1∣xi=0}=q\operatorname{Pr}\{x_{i+1}=1\mid x_i=0\}=q, Pr⁡{xi+1=1∣xi=1}=p\operatorname{Pr}\{x_{i+1}=1\mid x_i=1\}=p. It is obvious that Pr⁡{xi+1=1∣…}=1−Pr⁡{xi+1=0∣…}\operatorname{Pr}\{x_{i+1}=1\mid\ldots\}=1-\operatorname{Pr}\{x_{i+1}=0\mid\ldots\}, and these probabilities are not contained in the matrices.

\begin{array}{c|cccc} & \multicolumn{4}{c}{\text{probability of zero}}\\ s=2:\quad& p & q & q & p\\ \text{after} & 00 & 01 & 10 & 11 \tag*{(2)} \end{array}

This means that Pr⁡{xi+1=0∣xi−1xi=00}=p\operatorname{Pr}\{x_{i+1}=0\mid x_{i-1}x_i=00\}=p, etc.

The “typical” sequences for (1) and (2) for large pp (say, 0.90.9) can be as follows:

x1x2x3x4x5x6x7x8x9x10=0000111111,(3)x_1x_2x_3x_4x_5x_6x_7x_8x_9x_{10}=0000111111, \tag*{(3)}
x1x2x3x4x5x6x7x8x9x10=0000110110.(4)x_1x_2x_3x_4x_5x_6x_7x_8x_9x_{10}=0000110110. \tag*{(4)}

(In both cases, a rare event, i.e., with probability qq, occurred after x4x_4.)

Intuitive description of the ideas underlying the proposed method

In this article, we will consider transmission over two binary channels that are very popular in information theory: the binary erasure channel (BEC) and the binary symmetric channel (BSC).

For the first channel, any transmitted letter from {0,1}\{0,1\} is lost, i.e., the receiver receives a special symbol ∗\ast (instead of the transmitted 0 or 1) with a certain probability π\pi. For BSC, any letter from the sender can be replaced by another with a certain probability π\pi, see [17].

Now let us assume that a binary sequence is transmitted via BEC with probability π\pi, that is, any letter is converted to ∗\ast during transmission with probability π\pi.

Let us consider three cases:

i) The transmitted sequence is generated by a Bernoulli source B(p)B(p), p>1/2p>1/2. Obviously, the best strategy is to replace ∗\ast with 0, since the probability of 0 is equal to p>1/2p>1/2. Thus, Pr⁡(error)=q\operatorname{Pr}(\text{error}) = q. In the future, we will use the same strategy for all cases, that is, we will choose the letter with the higher posterior probability and, so, Pr⁡(error)\operatorname{Pr}(\text{error}) will be equal to the smaller probability.

ii) Consider the case where the sequence generated by a two-faced process is transmitted over the BEC. Suppose that the memory of the process is equal to 1, and the transmitted sequence (3) is received as

0 0 ∗ 0 1 1 1 ∗ 1 1.(5)0\ 0\ *\ 0\ 1\ 1\ 1\ *\ 1\ 1. \tag*{(5)}

(That is, the third and eighth letters are erased.) Since x2=0x_2=0 and x4=0x_4=0, a direct calculation using (1) and Bayes’ rule gives

P(x3=0∣(5))=P(x3=0∣x2=0)P(x4=0∣x3=0)P(x3=0∣x2=0)P(x4=0∣x3=0)+P(x3=1∣x2=0)P(x4=0∣x3=1)=p2p2+q2.P(x_3=0\mid(5)) = \frac{P(x_3=0\mid x_2=0)P(x_4=0\mid x_3=0)} {P(x_3=0\mid x_2=0)P(x_4=0\mid x_3=0)+P(x_3=1\mid x_2=0)P(x_4=0\mid x_3=1)} = \frac{p^2}{p^2+q^2}.

Thus, in this case, Pr⁡(error)=P(x3=1∣(5))=q2/(p2+q2)\operatorname{Pr}(\text{error})=P(x_3=1\mid(5))=q^2/(p^2+q^2). The same is true for the eighth letter.

iii) Now suppose that the memory of the two-faced process is 2 and sequence (4) was transmitted via the same BEC and the following was received:

0 0 ∗ 0 1 1 0 ∗ 1 0.(6)0\ 0\ *\ 0\ 1\ 1\ 0\ *\ 1\ 0. \tag*{(6)}

A direct calculation of conditional probabilities using (2) shows that P(x3=0∣(6))=p3/(p3+q3)P(x_3=0\mid(6))=p^3/(p^3+q^3). Thus, in this case, Pr⁡(error)=q3/(p3+q3)\operatorname{Pr}(\text{error})=q^3/(p^3+q^3). The same is true for the eighth letter.

So, from these simple examples, we see that the probability of error is qq for a Bernoulli process and q2/(p2+q2)q^2/(p^2+q^2), q3/(p3+q3)q^3/(p^3+q^3) for two-faced processes with memory one and two, respectively. Thus, in this example, we see that increasing the memory of the process reduces the decoding error (in these examples, we do not consider all possible channel error positions, but later we will consider general methods and evaluate their performance). Thus, in a sense, increasing the memory corrects most of the channel errors.

The second ingredient of the proposed error correction method is the availability of a method for transforming the Bernoulli process (and any other random process) into a two-faced process with the necessary memory.

In short, the proposed coding scheme is a two-step procedure: first, the transmitted sequence is converted into a two-faced process and transmitted over a noisy channel. The resulting data is then adjusted according to maximum likelihood estimates, and the resulting sequence is transformed from a two-faced process back into an estimate of the original process.

For sources without redundancy (such as B(1/2)B(1/2)), the stretching code described later in Section VIII uses a three-step procedure: first, additional symbols (say, zeroes) are added to the original sequence. Then, the resulting sequence is converted into a two-faced process, and finally, the sequence received over the channel is decoded and converted back into an estimate of the original Bernoulli process (where the decoder knows the positions of the added characters).

Two-faced processes and transformations

Two-faced processes

Let us define matrices T1=(pq01)T_1 = \begin{pmatrix} p & q \\ 0 & 1 \end{pmatrix}, T‾1=(qp01)\overline{T}_1 = \begin{pmatrix} q & p \\ 0 & 1 \end{pmatrix}, T2=T1∥T‾1=(pqqp00011011)T_2 = T_1 \mathbin\Vert\overline{T}_1 = \begin{pmatrix} p & q & q & p \\ 00 & 01 & 10 & 11 \end{pmatrix}, T‾2=(qppq00011011)\overline{T}_2 = \begin{pmatrix} q & p & p & q \\ 00 & 01 & 10 & 11 \end{pmatrix}, T3=T2∥T‾2T_3 = T_2 \mathbin\Vert\overline{T}_2, …\ldots, Tk+1=Tk∥T‾kT_{k+1} = T_k \mathbin\Vert\overline{T}_k, and so on. For example,

T‾3=(qppqpqqp000001010011100101110111),\overline{T}_3 = \begin{pmatrix} q & p & p & q & p & q & q & p \\ 000 & 001 & 010 & 011 & 100 & 101 & 110 & 111 \end{pmatrix},

where, as before, Pr⁡{xi+1=0∣xi−2xi−1xi=000}=q\Pr\{x_{i+1}=0 \mid x_{i-2}x_{i-1}x_i=000\}=q, etc.

More precisely, T‾k\overline{T}_k is obtained from TkT_k by swapping pp and qq in the top row of TkT_k, and the upper row of Tk+1T_{k+1} is a concatenation of the upper rows of TkT_k and T‾k\overline{T}_k, while the lower row is a sequence of lexicographically ordered words from {0,1}k+1\{0,1\}^{k+1}.

These processes were proposed by the author in 2004, and a complete description of them can be found in [15]. There, it was proven that for a process with memory ss, for any r≤sr \le s and any word gg of length rr, Pr⁡{xi…xi+r−1=g}=2−r\Pr\{x_i \ldots x_{i+r-1}=g\}=2^{-r}, whereas the Shannon entropy per symbol h∞h_\infty is equal to −(plog⁡2p+qlog⁡2q)-(p\log_2 p+q\log_2 q), i.e., h∞h_\infty can be very small (for large pp). This is why such processes are called two-faced: if we look at the frequencies of words of length r≤sr \le s, the process appears to be uniformly distributed (i.e., “completely random”), but if we look at the frequencies of long words (those longer than ss), this distribution is very far from uniform.

Two-faced transformations

First, we define two maps φl,w:{0,1}n→{0,1}n\varphi_{l,w}:\{0,1\}^{n}\to\{0,1\}^{n} and ψl,w:{0,1}n→{0,1}n\psi_{l,w}:\{0,1\}^{n}\to\{0,1\}^{n}, where integers n,ln,l (l≤nl\le n) and a word w∈{0,1}lw\in\{0,1\}^{l} are parameters. Let there be given words w=w1…wl∈{0,1}lw=w_{1}\ldots w_{l}\in\{0,1\}^{l} and x1…xn∈{0,1}nx_{1}\ldots x_{n}\in\{0,1\}^{n}.

The transformation φl,w:x→v\varphi_{l,w}:x\to v is defined by the initial conditions vj=wl+jv_{j}=w_{l+j} for j=−l+1,…,0j=-l+1,\ldots,0, and

vi={xiif ∑j=i−li−1vj is even,xi‾if ∑j=i−li−1vj is odd,v_i = \begin{cases} x_i & \text{if } \sum_{j=i-l}^{i-1}v_j\text{ is even},\\ \overline{x_i} & \text{if } \sum_{j=i-l}^{i-1}v_j\text{ is odd}, \end{cases}

for i=1,…,ni=1,\ldots,n (here and below 0‾=1\overline{0}=1, 1‾=0\overline{1}=0).

It will be convenient to use the following notations: a⊕b=(a+b) mod 2a\oplus b=(a+b)\bmod2 and ⨁i=mnxi=xm⊕⋯⊕xn\bigoplus_{i=m}^{n}x_i=x_m\oplus\cdots\oplus x_n. Thus, the transformation φl,w:x→v\varphi_{l,w}:x\to v can be rewritten as follows:

vi=xi⊕⨁j=i−li−1vj(7)v_i=x_i\oplus\bigoplus_{j=i-l}^{i-1}v_j \tag*{(7)}

for i=1,…,ni=1,\ldots,n. For an nn-bit word vv (with v−l+1…v0=w1…wlv_{-l+1}\ldots v_0=w_1\ldots w_l), the inverse transformation ψl,w:v→u\psi_{l,w}:v\to u is defined by

ui+1=vi+1⊕⨁j=i−l+1ivj(8)u_{i+1}=v_{i+1}\oplus\bigoplus_{j=i-l+1}^{i}v_j \tag*{(8)}

for i=0,…,n−1i=0,\ldots,n-1. For example, for the sequence x=0000100000x=0000100000, φ1,0(x)\varphi_{1,0}(x) equals 00001111110000111111, φ2,00(x)\varphi_{2,00}(x) equals 00001101100000110110, ψ1,0(0000111111)=0000100000\psi_{1,0}(0000111111)=0000100000, and ψ2,00(0000110110)=0000100000\psi_{2,00}(0000110110)=0000100000.

Note that ψl,w(φl,w(x))=x\psi_{l,w}(\varphi_{l,w}(x))=x.

The following theorem from [15] holds for the transformation φl,w(x)\varphi_{l,w}(x):

Theorem 1. Let l>0l>0 be an integer, ww be a uniformly distributed binary word of ll letters, and let x=x1…xnx=x_1\ldots x_n be generated randomly according to a Bernoulli process with parameters

p∈(0,1)p \in(0,1). Then the sequence φl,w(x)\varphi_{l,w}(x) obeys the distribution of a two-faced process TlT_l of order ll (with matrix TlT_l) and probability pp.

Comment. In this paper, we will focus on the Bernoulli process, but a similar theorem holds not only for the Bernoulli process but also for any stochastic one (see [15], Theorem 4).

Code structure

Let us describe the encoders for BEC and BSC. In all cases, we will consider the following scheme. There is an integer ll and a word w∈{0,1}lw \in\{0,1\}^{l}, formed according to a uniform distribution, where this word ww and integer ll are known to the sender and receiver. In addition, there is a word x=x1…xnx = x_1 \ldots x_n generated by a Bernoulli source B(p)B(p), and this word must be transmitted over a noisy channel. (Of course, xx is unknown to the receiver.)

The case where l=nl=n is of particular interest, since in this case the codewords v1…vnv_1 \ldots v_n are uniformly distributed. (Recall that ww is also uniformly distributed. In practice, it may be difficult to store the same value of ww in both the encoder and the decoder; however, the same pseudorandom number generator can be used for both.)

Let us denote φl,w(x)=v1…vn\varphi_{l,w}(x)=v_1\ldots v_n. Define the word v=w1…wlv1…vnv=w_1\ldots w_l v_1\ldots v_n, that is, vv is a word of (n+l)(n+l) letters, and v−l+1…v0=w1…wlv_{-l+1}\ldots v_0=w_1\ldots w_l. The word v1…vnv_1\ldots v_n is transmitted over a noisy channel, and the receiver receives a distorted word v1∗,…,vn∗v_1^*,\ldots,v_n^*. Note that in the case of BEC, vi∗∈{0,1,∗}v_i^* \in\{0,1,*\}. It is convenient to define v−l+1∗…v0∗v_{-l+1}^*\ldots v_0^* as w1…wlw_1\ldots w_l. (This is possible because the word ww is known to the receiver.) Thus, v−l+1∗…v0∗=v−l+1…v0v_{-l+1}^*\ldots v_0^*=v_{-l+1}\ldots v_0.

Decoding is a two-step procedure: first, the sequence v∗=v1∗v2∗…vn∗v^*=v_1^*v_2^*\ldots v_n^* is processed into the sequence v′=v1′v2′…vn′v'=v_1'v_2'\ldots v_n' in the hope of eliminating some errors (but, at the same time, possibly adding new ones). Then the mapping ψl,w(v′)\psi_{l,w}(v') is applied, and the resulting sequence x′=x1′…xn′x'=x_1'\ldots x_n' is the result of decoding. Here, the transformation v1∗v2∗…vn∗→v1′v2′…vn′v_1^*v_2^*\ldots v_n^* \to v_1'v_2'\ldots v_n' plays a key role and will be described in the next section.

Another important quantity is the bit error rate (BER), defined as the average frequency of symbols for which xi′≠xix_i' \ne x_i, i=1,…,ni=1,\ldots,n. We denote it as BER(Code)BER(Code), where CodeCode is a specific coding method.

Maximum likelihood decoding for BSC and BEC

Decoding scheme

First, let us give a definition. Given the known initial state v−l+1…v0v_{-l+1} \ldots v_0 and the received sequence v1∗…vn∗v_1^* \ldots v_n^*, the maximum likelihood (MAP) decoder determines the estimate v1′…vn′v_1' \ldots v_n' as follows:

v1′…vn′=arg⁡max⁡v1…vn∈{0,1}nP(v1…vn∣v−l+1…v0,v1∗…vn∗)(9)v_1' \ldots v_n' = \arg\max_{v_1 \ldots v_n \in\{0,1\}^n} P(v_1 \ldots v_n \mid v_{-l+1} \ldots v_0, v_1^* \ldots v_n^*) \tag*{(9)}

Since the channel is memoryless and P(v1∗…vn∗∣v−l+1…v0)P(v_1^* \ldots v_n^* \mid v_{-l+1} \ldots v_0) does not depend on v1…vnv_1 \ldots v_n, by Bayes’ rule and the Markov property of order ll, maximizing (9) is equivalent to

v1′…vn′=arg⁡max⁡v1…vn∈{0,1}n∏i=1nP(vi∗∣vi)P(vi∣vi−l…vi−1)(10)v_1' \ldots v_n' = \arg\max_{v_1 \ldots v_n \in\{0,1\}^n} \prod_{i=1}^{n} P(v_i^* \mid v_i)P(v_i \mid v_{i-l} \ldots v_{i-1}) \tag*{(10)}

where P(vi∗∣vi)P(v_i^* \mid v_i) is the channel transition probability (for BEC, P(∗∣vi)=πP(* \mid v_i) = \pi and P(vi∣vi)=1−πP(v_i \mid v_i) = 1-\pi; for BSC, P(1−vi∣vi)=πP(1-v_i \mid v_i) = \pi and P(vi∣vi)=1−πP(v_i \mid v_i) = 1-\pi). If a decoder is designed for a Markov chain of memory ll, we denote it as DeclDec_l.

Example: the case where l=1

Let l=1l=1, and let us describe the dynamic programming algorithm for computing v1′…vn′v_1' \ldots v_n' in (10).

To describe the decoder Dec1Dec_1, for each step s=1,…,ns=1,\ldots,n and each state a∈{0,1}a \in\{0,1\} (representing the value of vs−1v_{s-1}), we define the maximum suffix probability μn,sa\mu_{n,s}^a and the optimal next symbol Vsa∈{0,1}V_s^a \in\{0,1\}. For s=ns=n and a∈{0,1}a \in\{0,1\}, let

μn,na=max⁡z∈{0,1}{P(vn∗∣vn=z)P(vn=z∣vn−1=a)},\mu_{n,n}^a = \max_{z \in\{0,1\}} \left\{P(v_n^* \mid v_n=z)P(v_n=z \mid v_{n-1}=a)\right\},
Vna=arg⁡max⁡z∈{0,1}{P(vn∗∣vn=z)P(vn=z∣vn−1=a)}(11)V_n^a = \arg\max_{z \in\{0,1\}} \left\{P(v_n^* \mid v_n=z)P(v_n=z \mid v_{n-1}=a)\right\} \tag*{(11)}

For s=n−1,n−2,…,1s=n-1,n-2,\ldots,1 and a∈{0,1}a \in\{0,1\}, we define recursively

μn,sa=max⁡z∈{0,1}{P(vs∗∣vs=z)P(vs=z∣vs−1=a)μn,s+1z},\mu_{n,s}^a = \max_{z \in\{0,1\}} \left\{P(v_s^* \mid v_s=z)P(v_s=z \mid v_{s-1}=a)\mu_{n,s+1}^z\right\},
Vsa=arg⁡max⁡z∈{0,1}{P(vs∗∣vs=z)P(vs=z∣vs−1=a)μn,s+1z}(12)V_s^a = \arg\max_{z \in\{0,1\}} \left\{P(v_s^* \mid v_s=z)P(v_s=z \mid v_{s-1}=a)\mu_{n,s+1}^z\right\} \tag*{(12)}

The proposed algorithm Dec1Dec_1 works in two passes:

  1. Backward pass: It computes μn,s0,μn,s1,Vs0,Vs1\mu_{n,s}^0,\mu_{n,s}^1,V_s^0,V_s^1 step by step for s=n,n−1,…,1s=n,n-1,\ldots,1.

  1. Forward pass: Using the known initial symbol v0v_0, it reconstructs the sequence v1′…vn′v'_1 \ldots v'_n iteratively by setting

v1′=V1v0,vs′=Vsvs−1′for s=2,…,n.(13)v'_1=V_1^{v_0}, \qquad v'_s=V_s^{v'_{s-1}}\quad\text{for }s=2,\ldots,n. \tag*{(13)}

The following statement shows that the resulting sequence v1′…vn′v'_1\ldots v'_n is an optimal solution of (9) for l=1l=1.

Claim 1. Let v=v1…vnv=v_1\ldots v_n be the input sequence, and v1∗…vn∗v^*_1\ldots v^*_n be the output sequence of a memoryless noisy channel, where vv is generated by a Markov chain (1) with known initial state v0v_0. Then the output sequence v1′…vn′v'_1\ldots v'_n of the decoder Dec1\mathrm{Dec}_1 defined in (13) is a solution of (9).

Proof. For any s∈{1,…,n}s\in\{1,\ldots,n\} and a∈{0,1}a\in\{0,1\}, let us show by backward induction on ss that

μn,sa=max⁡bs…bn∈{0,1}n−s+1∏i=snP(vi∗∣vi=bi)P(vi=bi∣vi−1=bi−1),(14)\mu_{n,s}^{a}=\max_{b_s\ldots b_n\in\{0,1\}^{n-s+1}}\prod_{i=s}^{n}P(v_i^*\mid v_i=b_i)P(v_i=b_i\mid v_{i-1}=b_{i-1}), \tag*{(14)}

where bs−1=ab_{s-1}=a, and that the sequence bs′…bn′b'_s\ldots b'_n constructed via bs′=Vsab'_s=V_s^a and bi′=Vibi−1′b'_i=V_i^{b'_{i-1}} (i=s+1,…,n)(i=s+1,\ldots,n) achieves this maximum.

For the base case s=ns=n, (14) holds directly by definition (11). Suppose that the claim holds for s+1s+1 (1≤s≤n−1)(1\le s\le n-1). Then for step ss and any a∈{0,1}a\in\{0,1\} (with bs−1=ab_{s-1}=a), we have

max⁡bs…bn∈{0,1}n−s+1∏i=snP(vi∗∣vi=bi)P(vi=bi∣vi−1=bi−1)=max⁡bs∈{0,1}{P(vs∗∣vs=bs)P(vs=bs∣vs−1=a)max⁡bs+1…bn∈{0,1}n−s∏i=s+1nP(vi∗∣vi=bi)P(vi=bi∣vi−1=bi−1)}=max⁡bs∈{0,1}{P(vs∗∣vs=bs)P(vs=bs∣vs−1=a)μn,s+1bs}=μn,sa,\begin{aligned} &\max_{b_s\ldots b_n\in\{0,1\}^{n-s+1}}\prod_{i=s}^{n}P(v_i^*\mid v_i=b_i)P(v_i=b_i\mid v_{i-1}=b_{i-1}) \\ &=\max_{b_s\in\{0,1\}}\left\{P(v_s^*\mid v_s=b_s)P(v_s=b_s\mid v_{s-1}=a) \max_{b_{s+1}\ldots b_n\in\{0,1\}^{n-s}}\prod_{i=s+1}^{n}P(v_i^*\mid v_i=b_i)P(v_i=b_i\mid v_{i-1}=b_{i-1})\right\}\\ &=\max_{b_s\in\{0,1\}}\left\{P(v_s^*\mid v_s=b_s)P(v_s=b_s\mid v_{s-1}=a)\mu_{n,s+1}^{b_s}\right\}=\mu_{n,s}^{a}, \end{aligned}

where the second equality follows from the induction hypothesis, and the last equality follows from (12). Moreover, by (12), the outer maximum is achieved at bs′=Vsab'_s=V_s^a, and by the induction hypothesis, the inner maximum is achieved by continuing with bi′=Vibi−1′b'_i=V_i^{b'_{i-1}} for i=s+1,…,ni=s+1,\ldots,n.

Setting s=1s=1 and a=v0a=v_0 in (14), we conclude that v1′…vn′v'_1\ldots v'_n given by (13) maximizes (10), and therefore is a solution of (9).

General case: l>1l > 1

We now generalize the algorithm above to any memory order l≥1l \ge1.

For a binary word u=u1u2…ul∈{0,1}lu = u_1u_2 \ldots u_l \in\{0,1\}^l and a symbol z∈{0,1}z \in\{0,1\}, let σ(u,z)=u2…ulz∈{0,1}l\sigma(u,z) = u_2 \ldots u_lz \in\{0,1\}^l denote the shifted window of length ll (for l=1l = 1, σ(u,z)=z\sigma(u,z) = z).

For each step s=1,…,ns = 1,\ldots,n and each state u∈{0,1}lu \in\{0,1\}^l (representing the context vs−l…vs−1v_{s-l}\ldots v_{s-1}), we define the real numbers μn,su\mu_{n,s}^u and the optimal next symbols Vsu∈{0,1}V_s^u \in\{0,1\}. For s=ns = n and u∈{0,1}lu \in\{0,1\}^l, let

μn,nu=max⁡z∈{0,1}{P(vn∗∣vn=z)P(vn=z∣vn−l…vn−1=u)},Vnu=arg⁡max⁡z∈{0,1}{P(vn∗∣vn=z)P(vn=z∣vn−l…vn−1=u)}.(15)\begin{aligned} \mu_{n,n}^u &= \max_{z\in\{0,1\}}\left\{P(v_n^* \mid v_n = z)P(v_n = z \mid v_{n-l}\ldots v_{n-1} = u)\right\},\\ V_n^u &= \arg\max_{z\in\{0,1\}}\left\{P(v_n^* \mid v_n = z)P(v_n = z \mid v_{n-l}\ldots v_{n-1} = u)\right\}. \tag*{(15)} \end{aligned}

For s=n−1,n−2,…,1s = n-1,n-2,\ldots,1 and u∈{0,1}lu \in\{0,1\}^l, we define

μn,su=max⁡z∈{0,1}{P(vs∗∣vs=z)P(vs=z∣vs−l…vs−1=u)μn,s+1σ(u,z)},Vsu=arg⁡max⁡z∈{0,1}{P(vs∗∣vs=z)P(vs=z∣vs−l…vs−1=u)μn,s+1σ(u,z)}.(16)\begin{aligned} \mu_{n,s}^u &= \max_{z\in\{0,1\}}\left\{P(v_s^* \mid v_s = z)P(v_s = z \mid v_{s-l}\ldots v_{s-1} = u)\mu_{n,s+1}^{\sigma(u,z)}\right\},\\ V_s^u &= \arg\max_{z\in\{0,1\}}\left\{P(v_s^* \mid v_s = z)P(v_s = z \mid v_{s-l}\ldots v_{s-1} = u)\mu_{n,s+1}^{\sigma(u,z)}\right\}. \tag*{(16)} \end{aligned}

The decoder Decl\mathit{Dec}_l operates as follows:

  1. Backward pass: It computes μn,su\mu_{n,s}^u and VsuV_s^u for all u∈{0,1}lu \in\{0,1\}^l step by step for s=n,n−1,…,1s = n,n-1,\ldots,1.

  1. Forward pass: Using the known initial state v−l+1…v0v_{-l+1}\ldots v_0 (setting vj′=vjv'_j = v_j for j=−l+1,…,0j=-l+1,\ldots,0), it reconstructs v1′…vn′v'_1\ldots v'_n iteratively by

vs′=Vsvs−l′…vs−1′for s=1,…,n.(17)v'_s = V_s^{v'_{s-l}\ldots v'_{s-1}} \qquad\text{for } s=1,\ldots,n. \tag*{(17)}

Theorem 2. Let v=v1…vnv = v_1\ldots v_n be the input sequence, and v1∗…vn∗v_1^*\ldots v_n^* be the output sequence of a memoryless noisy channel, where vv is generated by a Markov chain with memory l≥1l \ge1 and known initial state v−l+1…v0v_{-l+1}\ldots v_0. Then:

i) The output sequence v1′…vn′v'_1\ldots v'_n of the decoder Decl\mathit{Dec}_l given by (17) is a solution of (9).

ii) The runtime of Decl\mathit{Dec}_l is O(2ln)O(2^l n).

Proof. Statement i) follows by repeating the backward induction proof of Claim 1 with the state a∈{0,1}a \in\{0,1\} replaced by the ll-bit context u∈{0,1}lu \in\{0,1\}^{l}, the state transition bsb_s replaced by the window shift σ(u,bs)\sigma(u,b_s), and equations (15)–(17) used instead of (11)–(13).

For statement ii), at each of the nn steps s=n,…,1s = n,\ldots,1, the backward pass evaluates (16) for all 2l2^{l} words u∈{0,1}lu \in\{0,1\}^{l}, performing O(1)O(1) arithmetic operations per word. The forward pass (17) takes O(n)O(n) operations. Hence, the total runtime is O(2ln)O(2^{l}n).

Experiments

To compare codes practically, we conducted several experiments of programmatic implementation of described codes. We measured bit error rate (BER) for erasure (BEC) and symmetrical (BSC) channels. For BEC, channel error probability π\pi is probability that symbol will be erased, and for BSC π\pi is probability that symbol will be flipped. Also, in this section we assume p=P(1)p = P(1). Figures 1 and 2 show the measured bit error rate (BER) for p∈{0.0015,0.015,0.05,0.15,0.3}p \in\{0.0015, 0.015, 0.05, 0.15, 0.3\} and memory orders l∈{2,4,16}l \in\{2, 4, 16\}. For each source probability and channel, we tested all possible values of the channel error probability π\pi. For each test, we encoded and decoded k=256k = 256 blocks of n=2048n = 2048 bits and checked correctness. Error bars show the upper endpoints of 95% Wilson intervals [16], including when no errors were observed.

Plots are based on data which is published at github.com/zpix1/twofaced-decoding-methods-data.

For the BEC, the dashed reference line is pπp\pi, the uncoded BER when the receiver replaces erased bits with zero.

For the BSC, the dashed reference line gives the optimal uncoded BER min⁡(π,p)\min(\pi,p) for p≤1/2p \le1/2 and 0≤π≤1/20 \le\pi\le1/2. The uncoded receiver keeps the received bit when π≤p\pi\le p and always outputs zero when π>p\pi> p.

For each pp, Tables I and II show intervals where code was better than reference.

ppGain range in π\pill
0.0015≤0.2933\le0.29332, 4, 16
0.015≤0.2675\le0.26754, 16
0.05≤0.2201\le0.22012, 4, 16
0.15≤0.1282\le0.128216
0.3≤5.195×10−4\le5.195 \times10^{-4}16

Table I. BEC improvement range (relative to pπp\pi)

ppGain range in π\pill
0.0015≤0.1385\le0.13852, 4, 16
0.015≤0.1773\le0.17734, 16
0.05≤0.1164\le0.116416

Table II. BSC improvement range (relative to min⁡(π,p)\min(\pi,p))

BER for TF MLE on the BEC

Figure 1. BER for TF MLE on the BEC.

BER for TF MLE on the BSC

Figure 2. BER for TF MLE on the BSC.

Expanding the Scope of Application

Extension of the Bernoulli distribution B(p)B(p) for any value of pp

The experimental results in Section VII show that the described code does not reduce the error rate for all pairs of source and channel parameters. For example, if p=1/2p = 1/2, the proposed code—like any other—cannot be applied without increasing the length of the input sequence (typically by adding parity bits).

Obviously, the sender cannot change the channel error value. The only option is to encode the output sequence in such a way as to change the value of the parameter pp. (Of course, it must be possible to decode the encoded sequence back.)

So, we describe a code designed to stretch the original sequence satisfying the condition B(1/2)B(1/2) in such a way that the encoded sequences are close to the sequences generated by B(p)B(p), p≠1/2p \ne1/2, with the required pp.

Let us consider the transformation of sequences from B(1/2)B(1/2) to B(p)B(p), where p∈(0,1/2)p \in(0,1/2). First, let us describe the coding scheme. Let the initial sequence x=x1…x = x_1 \ldots be generated by a Bernoulli source B(1/2)B(1/2). The sequence xx is divided into sub-sequences y1=x1…xmy_1 = x_1 \ldots x_m, y2=xm+1…x2my_2 = x_{m+1} \ldots x_{2m}, …\ldots, where the integer mm is a parameter of the method. Then we define the set of kk-letter binary words with ss ones as C(k,s)C(k,s) and determine the minimum kk for which 2m≤∣C(k,⌊kp⌋)∣2^m \le|C(k,\lfloor kp\rfloor)|. Then the encoder ρ\rho is a mapping from {0,1}m→C(k,⌊kp⌋)\{0,1\}^m \to C(k,\lfloor kp\rfloor), whereas the decoder ρ−1\rho^{-1} is such a mapping from the set ρ({0,1}m)\rho(\{0,1\}^m) into {0,1}m\{0,1\}^m that ρ−1(ρ(u))=u\rho^{-1}(\rho(u)) = u for any u∈{0,1}mu \in\{0,1\}^m.

The decoding and encoding problems are well known in information theory, where they are often referred to as enumeration problems. For both problems, there exists an algorithm with a computational time and memory complexity of O(mlog⁡m)O(m \log m) (see [18] or the general enumeration method in [19]).

Extension to any stochastic processes

Let us briefly and informally discuss how the results obtained can be applied to general stochastic processes. As we mentioned above, the two-faced transformation can be applied to any stochastic process, so the encoder can be used as described above. The described maximum likelihood decoding process can be applied directly if the decoder uses the conditional probabilities of the process.

Conclusion

The error-correcting code proposed here performs encoding and decoding at a constant rate and requires a memory capacity of approximately 282^{8}–2162^{16} cells, which is quite acceptable for modern processors. Given this, it can be said that its use requires virtually no additional resource overhead. Thus, this code can be used when transmitting redundant data over low-noise channels to reduce the bit error rate (BER) by a factor of several, while employing relatively simple encoders and decoders. This simplicity allows the code to be used in combination with other joint source-channel coding (JSCC) methods, though this may require further research.

References

  1. [1]Shannon CE. A mathematical theory of communication. The Bell system technical journal. 1948 Jul;27(3):379-423.
  2. [2]Moon TK. Error correction coding: mathematical methods and algorithms. John Wiley & Sons; 2020 Dec 15.
  3. [3]Etzion T. Perfect codes and related structures. 2022 Mar 14.DOI
  4. [4]Berlekamp ER. The performance of block codes. Notices of the AMS. 2002 Jan;49(1):17-22.
  5. [5]Wicker SB, Bhargava VK, Reed-Solomon codes and their applications. John Wiley & Sons; 1999 Oct 12.DOI
  6. [6]Johannesson R, Zigangirov KS. Fundamentals of convolutional coding. John Wiley & Sons; 2015.
  7. [7]Tretter SA. Introduction to Bose Chaudhuri Hocquenghem codes. 1967 Sep 1.
  8. [8]Johnson SJ. Introducing low-density parity-check codes. University of Newcastle, Australia. 2006.
  9. [9]Ryabko B. Linear hash functions and their applications to error detection and correction // Discrete Mathematics, Algorithms and Applications. - 2024. - Vol.16. - Iss. 6. - Art.2350070.arxiv.org/abs/2008.08955
  10. [10]Fresia M, Pérez-Cruz F, Poor HV, Verdú S. Joint source and channel coding. IEEE Signal Processing Magazine. 2010 Oct 18;27(6):104-13.DOI
  11. [11]Gündüz D, Wigger MA, Tung TY, Zhang P, Xiao Y. Joint source–channel coding: Fundamentals and recent progress in practical designs. Proceedings of the IEEE. 2024 Nov 8.arxiv.org/abs/2409.17557
  12. [12]Sayood K, Borkenhagen JC. Use of residual redundancy in the design of joint source/channel coders. IEEE Transactions on Communications. 1991 Jun 30;39(6):838-46.DOI
  13. [13]Phamdo N, Farvardin N. Optimal detection of discrete Markov sources over discrete memoryless channels/spl minus/applications to combined source-channel coding. IEEE Transactions on Information Theory. 1994 Jan 31;40(1):186-93.
  14. [14]Hagenauer J. Source-controlled channel decoding. IEEE Transactions on Communications. 1995 Sep 30;43(9):2449-57.
  15. [15]Ryabko B. Low-entropy stochastic processes for generating k-distributed and normal sequences, and the relationship of these processes with random number generators. Mathematics. 2019 Sep 10;7(9):838.DOI
  16. [16]E. B. Wilson, “Probable inference, the law of succession, and statistical inference,” J. Amer. Stat. Assoc., vol. 22, no. 158, pp. 209–212, Jun. 1927, doi: 10.1080/01621459.1927.10502953.DOI
  17. [17]T. M. Cover and J. A. Thomas, Elements of information theory. New York, NY, USA: Wiley-Interscience, 2006.
  18. [18]V. F. Babkin, “A method of universal coding with non-exponent labour consumption,” Probl. Inform. Transmiss., vol. 7, pp. 13–21, Jun. 1971.
  19. [19]Ryabko B. A General Method for the Development of Constrained Codes. IEEE Transactions on Information Theory, VOL. 71, NO. 5, MAY 2025, pp. 3510-3515.arxiv.org/abs/2405.14570

Paper details

vlnc:W_htka7f7e
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents