Justesen code - AbsoluteAstronomy.com

Introduction

Coding theory

Coding theory is the study of the properties of codes and their fitness for a specific application. Codes are used for data compression, cryptography, error-correction and more recently also for network coding...

, Justesen codes form a class of Error detection and correction codes

Error detection and correction

In information theory and coding theory with applications in computer science and telecommunication, error detection and correction or error control are techniques that enable reliable delivery of digital data over unreliable communication channels...

which are derived from Reed-Solomon code

Reed–Solomon error correction

In coding theory, Reed–Solomon codes are non-binary cyclic error-correcting codes invented by Irving S. Reed and Gustave Solomon. They described a systematic way of building codes that could detect and correct multiple random symbol errors...

and have good error-control properties. In code concatenation, we compose an outer code

with an inner code

. By using the appropriate outer and inner code

and

, we can obtain new bound for code, such as Zyablov bound

Zyablov bound

In coding theory, the Zyablov bound, is a lower bound on the rate R and relative distance \delta of the concatenated codes.-Statement of the bound:...

. The Justesen code composes the Reed-Solomon code

Reed–Solomon error correction

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

outer code

and different

inner codes

. More precisely, the concatenation of these codes, denoted by

, is defined as follows. Given a message

, we compute the codeword produced by an outer code

. Then we apply each code of N linear inner codes to each coordinate of that codeword to produce the final codeword; that is,

. 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

elements, and we have

linear inner codes to apply for those

elements.

Here for the Justesen code, the outer code

is chosen to be Reed Solomon code

Reed–Solomon error correction

over a field

Field (mathematics)

In abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...

evaluated over

of rate

Code rate

In telecommunication and information theory, the code rate of a forward error correction code is the proportion of the data-stream that is useful...

. The outer code

have the relative distance

and block length of

. The set of inner codes is the Wozencraft ensemble

Property of Justesen Code

As the linear codes in the Wonzencraft ensemble have the rate

, Justesen code is the concatenated code

with the rate

. We have the following theorem that estimates the distance of the concatenated code

Theorem

Let

> 0.

has relative distance at least

.

Proof:

The idea of proving that the code

has the distance at least

is to prove that the Hamming distance of two different codewords is at least

.

Denote

be the Hamming distance of two codewords

and

.

So for any given

and

(

), we want to lower bound

.

Notice that if

, then

. So to the lower bound

, we need to take into account the distance of

for i = 1,2,…,N.

Suppose

and

.

Recall that

is a Wozencraft ensemble. Due to "Wonzencraft ensemble theorem", there are at least

linear codes

that have distance

.

So if for some

and

code has distance

, then

.

Further, if we have

numbers

such that

and

code has distance

, then

.

So now the final task is to lower bound

.

Denote S be the set of all

(

) such that

. Then

is the number of linear codes

(

) having the distance

.

Now we want to estimate

. Obviously

.

Due to the Wozencraft Ensemble Theorem, there are at most

linear codes having distance less than

, so

.

Finally,we have

.

This is true for any arbitrary

. So

has the relative distance at least

, 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

is an asymptotically good code(that is, rate

> 0 and relative distance

> 0 for small q) and has a strongly explicit construction.

An example of a Justesen code

The following slightly different code is referred to as the Justesen code in MacWilliams/MacWilliams. It is the particular case of the above-considered
Justesen code for a very particular Wonzencraft ensemble:

Let R be a Reed-Solomon code of length N = 2^m − 1, rank

Dimension (vector space)

In mathematics, the dimension of a vector space V is the cardinality of a basis of V. It is sometimes called Hamel dimension or algebraic dimension to distinguish it from other types of dimension...

K and minimum weight N − K + 1. The symbols of R are elements of F = GF(2^m) and the codewords are obtained by taking every polynomial ƒ over F of degree less than K and listing the values of ƒ on the non-zero elements of F in some predetermined order. Let α be a primitive element of F. For a codeword a = (a₁, ..., a_N) from R, let b be the vector of length 2N over F given by

and let c be the vector of length 2N m obtained from b by expressing each element of F as a binary vector of length m. The Justesen code is the linear code containing all such c.

The parameters of this code are length 2m N, dimension m K and minimum distance

Minimum distance

The term minimum distance is used in several ways:* In geometry, the minimum distance of a collection of points P in a space is the smallest distance between any two points of the space....

at least

where

is the greatest integer satisfying

. (See MacWilliams/MacWilliams for a proof.)

Introduction

Definition

Property of Justesen Code

Theorem

Comments

An example of a Justesen code

See Also