Justesen code

Introduction

In coding theory, Justesen codes form a class of Error detection and correction codes which are derived from Reed-Solomon code and have good error-control properties. In code concatenation, we compose an outer code $C_{out}$ with an inner code $C_{in}$. By using the appropriate outer and inner code $C_{out}$ and $C_{in}$, we can obtain new bound for code, such as Zyablov bound. The Justesen code composes the Reed-Solomon code with the Wonzencraft ensemble and has a strongly explicit construction.Loosely speaking, the code has the strongly explicit construction if we can construct it in log space complexity. Unlike the usual code concatenation, the Justesen code obtains the power by using different linear inner codes as we see below.

Definition

Justesen code is concatenation code with different linear inner codes, which is composed of an $(N,K,D)_{q^{k}}$ outer code $C_{out}$ and different $(n,k,d)_{q}$ inner codes $C_{in}^{i}$, $1\leq i\leq N$. More precisely, the concatenation of these codes, denoted by $C_{out}\circ (C_{in}^{1},...,C_{in}^{N})$, is defined as follows. Given a message $m\in [q^{k}]^{K}$, we compute the codeword produced by an outer code $C_{out}$: $C_{out}(m)=(c_{1},c_{2},..,c_{N})$. Then we apply each code of N linear inner codes to each coordinate of that codeword to produce the final codeword; that is, $C_{out}\circ (C_{in}^{1},..,C_{in}^{N})(m)=(C_{in}^{1}(c_{1}),C_{in}^{2}(c_{2}),..,C_{in}^{n}(c_{N}))$. Look back to the definition of the outer code and linear inner codes, this definition of the Justesen code makes sense because the codeword of the outer code is a vector with $N$ elements, and we have $N$ linear inner codes to apply for those $N$ elements.

Here for the Justesen code, the outer code $C_{out}$ is chosen to be Reed Solomon code over a field $\mathbb {F} _{q^{k}}$ evaluated over $\mathbb {F} _{q^{k}}-\{0\}$ of rate $R$, $0$ < $R$ < $1$. The outer code $C_{out}$ have the relative distance $\delta _{out}=1-R$ and block length of $N=q^{k}-1$. The set of inner codes is the Wonzencraft ensemble $\{C_{in}^{\alpha }\}_{\alpha \in \mathbb {F} _{q^{k}}^{*}}$.

Property of Justesen Code

As the linear codes in the Wonzencraft ensemble have the rate ${\frac {1}{2}}$, Justesen code is the concatenated code $C^{*}=C_{out}\circ (C_{in}^{1},C_{in}^{2},..,C_{in}^{N})$ with the rate ${\frac {R}{2}}$. We have the following theorem that estimates the distance of the concatenated code $C^{*}$.

Theorem

Let $\varepsilon$ > 0. $C^{*}$ has relative distance at least $(1-R-\varepsilon )H_{q}^{-1}({\frac {1}{2}}-\varepsilon )$.

Proof:

The idea of proving that the code $C^{*}$ has the distance at least $(1-R-\varepsilon )H_{q}^{-1}({\frac {1}{2}}-\varepsilon )\cdot 2k\cdot N$ is to prove that the Hamming distance of two different codewords is at least $(1-R-\varepsilon )H_{q}^{-1}({\frac {1}{2}}-\varepsilon )\cdot 2k\cdot N$.

Denote $\Delta (c^{1},c^{2})$ be the Hamming distance of two codewords $c^{1}$ and $c^{2}$.

So for any given $m_{1}$ and $m_{2}$ in $(\mathbb {F} _{q^{k}})^{K}$ ($m_{1}\neq m_{2}$), we want to lower bound $\Delta (C^{*}(m_{1}),C^{*}(m_{2}))$.

Notice that if $C_{out}(m)=(c_{1},c_{2},..,c_{N})$, then $C^{*}(m)=(C_{in}^{1}(c_{1}),C_{in}^{2}(c_{2}),..,C_{in}^{N}(c_{N}))$. So to the lower bound $\Delta (C^{*}(m_{1}),C^{*}(m_{2}))$, we need to take into account the distance of $C_{in}^{i}$ for i = 1,2,…,N.

Suppose $C_{out}(m_{1})=(c_{1}^{1},c_{2}^{1},..,c_{N}^{1})$ and $C_{out}(m_{2})=(c_{1}^{2},c_{2}^{2},..,c_{N}^{2})$.

Recall that $\{C_{in}^{i}\}_{1\leq i\leq N}$ is a Wonzencraft ensemble. Due to "Wonzencraft ensemble theorem", there are at least $(1-\varepsilon )N$ linear codes $C_{in}^{i}$ that have distance $H_{q}^{-1}({\frac {1}{2}}-\varepsilon )\cdot 2k$.

So if for some $1\leq i\leq N$, $c_{i}^{1}\neq c_{i}^{2}$ and $C_{in}^{i}$ code has distance $\geq H_{q}^{-1}({\frac {1}{2}}-\varepsilon )\cdot 2k$, then $\Delta (C_{in}^{i}(c_{i}^{1}),C_{in}^{i}(c_{i}^{2}))\geq H_{q}^{-1}({\frac {1}{2}}-\varepsilon )\cdot 2k$.

Further, if we have $T$ numbers $1\leq i\leq N$ such that $c_{i}^{1}\neq c_{i}^{2}$ and $C_{in}^{i}$ code has distance $\geq H_{q}^{-1}({\frac {1}{2}}-\varepsilon )\cdot 2k$, then $\Delta (C^{*}(m_{1}),C^{*}(m_{2}))\geq H_{q}^{-1}({\frac {1}{2}}-\varepsilon )\cdot 2k\cdot T$.

So now the final task is to lower bound $T$.

Denote S be the set of all $i$ ($1\leq i\leq N$) such that $c_{i}^{1}\neq c_{i}^{2}$. Then $T$ is the number of linear codes $C_{in}^{i}$ ($i\in S$) having the distance $H_{q}^{-1}({\frac {1}{2}}-\varepsilon )\cdot 2k$.

Now we want to estimate $\left|S\right|$. Obviously $\left|S\right|=\Delta (C_{out}(m_{1}),C_{out}(m_{2}))\geq (1-R)N$.

Due to the Wonzencraft Ensemble Theorem, there are at most $\varepsilon N$ linear codes having distance less than $H_{q}^{-1}({\frac {1}{2}}-\varepsilon )\cdot 2k$, so $T\geq \left|S\right|-\varepsilon N\geq (1-R)N-\varepsilon N=(1-R-\varepsilon )N$.

Finally,we have

$\Delta (C^{*}(m_{1}),C^{*}(m_{2}))\geq H_{q}^{-1}({\frac {1}{2}}-\varepsilon )\cdot 2k\cdot T\geq H_{q}^{-1}({\frac {1}{2}}-\varepsilon )\cdot 2k\cdot (1-R-\varepsilon )\cdot N$.

This is true for any arbitrary $m_{1}\neq m_{2}$. So $C^{*}$ has the relative distance at least $(1-R-\varepsilon )H_{q}^{-1}({\frac {1}{2}}-\varepsilon )$, which completes the proof.

Comments

We want to consider the "strongly explicit code". So the question is what the "strongly explicit code" is. Loosely speaking, for linear code, the "explicit" property is related to the complexity of constructing its generator matrix G. That means, we can compute the matrix in logarithmic space without using the brute force algorithm to verify that a code has a given satisfied distance.

For the other codes that are not linear, we can consider the complexity of the encoding algorithm.

So by far, we can see that the Wonzencraft ensemble and Reed-Solomon codes are strongly explicit. Therefore we have the following result:

Corollary: The concatenated code $C^{*}$ is an asymptotically good code(that is, rate $R$ > 0 and relative distance $\delta$ > 0 for small q) and has a strongly explicit construction.

See Also

1. Wonzencraft Ensemble
2. Concatenated error correction code
3. Reed-Solomon error correction
4. Linear Code

References

1. Lecture 28: Justesen Code. Coding theory's course. Prof. Atri Rudra.
2. Lecture 6: Concatenated codes. Forney codes. Justesen codes. Essential Coding Theory.
3. J. Justesen (1972). "A class of constructive asymptotically good algebraic codes". IEEE Trans. Info. Theory. 18: 652–656. doi:10.1109/TIT.1972.1054893.
4. F.J. MacWilliams (1977). The Theory of Error-Correcting Codes. North-Holland. pp. 306–316. ISBN 0-444-85193-3. {{cite book}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)