Wozencraft ensemble

Wozencraft ensemble is a set of in which most of codes satisfy the . It is named after , who proved its existence. The ensemble is described by , who attributes it to Wozencraft. used the Wozencraft ensemble as the inner codes in his construction of strongly explicit asymptotically good code.

1 Existence theorem
2 Proof
3 See also
4 Source

Existence theorem

Theorem: Let

varepsilon > 0.

For a large enough

k

, there exists an ensemble of inner codes

C_{in}^1,cdots,C_{in}^N

tfrac{1}{2}

, where

N = q^k - 1

, such that for at least

(1 - varepsilon)N

values of

i, C_{in}^i

has relative distance

geqslant H_q^{ - 1} left(tfrac{1}{2} - varepsilon right )

Here relative distance is the ratio of minimum distance to block length. And $H_q$ is the q-ary entropy function defined as follows:

H_q(x) = xlog_q(q-1)-xlog_qx-(1-x)log_q(1-x).

In fact, to show the existence of this set of linear codes, we will specify this ensemble explicitly as follows: for $alpha in mathbb{F}_{q^k } - { 0}$ , define the inner code

begin{cases} C_{in}^alpha :mathbb{F}_q^k to mathbb{F}_q^{2k} \ C_{in}^alpha (x) = (x,alpha x) end{cases}

Here we can notice that $x in mathbb{F}_q^k$ and $alpha in mathbb{F}_{q^k}$ . We can do the multiplication $alpha x$ since $mathbb{F}_q^k$ is isomorphic to $mathbb{F}_{q^k}$ .

This ensemble is due to Wozencraft and is called the Wozencraft ensemble.

For all $x, y in mathbb{F}_q^k$ , we have the following facts:

$C_{in}^alpha (x) + C_{in}^alpha (y) = (x,alpha x)+(y,alpha y) = (x + y,alpha (x + y)) = C_{in}^alpha (x + y)$
For any $a in mathbb{F}_q, aC_{in}^alpha (x) = a(x,alpha x) = (ax,alpha (ax)) = C_{in}^alpha (ax)$

So $C_{in}^alpha$ is a linear code for every $alpha in mathbb{F}_{q^k } - { 0}$ .

Now we know that Wozencraft ensemble contains linear codes with rate $tfrac{1}{2}$ . In the following proof, we will show that there are at least $(1 - varepsilon)N$ those linear codes having the relative distance $geqslant H_q^{ - 1} left (tfrac{1}{2} - varepsilon right )$ , i.e. they meet the Gilbert-Varshamov bound.

Proof

To prove that there are at least $(1-varepsilon)N$ number of linear codes in the Wozencraft ensemble having relative distance $geqslant H_q^{-1}left(tfrac{1}{2}-varepsilon right)$ , we will prove that there are at most $varepsilon N$ number of linear codes having relative distance $< H_q^{-1}left(tfrac{1}{2}-varepsilon right)$ i.e., having distance $< H_q^{-1}left(tfrac{1}{2}-varepsilon right) cdot 2k.$

Notice that in a linear code, the distance is equal to the minimum weight of all codewords of that code. This fact is the . So if one non-zero codeword has weight $< H_q^{-1}left(tfrac{1}{2}-varepsilon right) cdot 2k$ , then that code has distance $< H_q^{-1}left(tfrac{1}{2}-varepsilon right) cdot 2k.$

Let $P$ be the set of linear codes having distance $< H_q^{-1}left(tfrac{1}{2}-varepsilon right) cdot 2k.$ Then there are $|P|$ linear codes having some codeword that has weight $< H_q^{-1}left(tfrac{1}{2}-varepsilon right) cdot 2k.$

Lemma. Two linear codes

C_{in}^{alpha_1}

and

C_{in}^{alpha_2}

with

alpha_1, alpha_2 in mathbb{F}_{q^k}

distinct and non-zero, do not share any non-zero codeword.

Proof. Suppose there exist distinct non-zero elements

alpha_1, alpha_2 in mathbb{F}_{q^k}

such that the linear codes

C_{in}^{alpha_1}

and

C_{in}^{alpha_2}

contain the same non-zero codeword

y.

Now since

y in C_{in}^{alpha_1}, y = (y_1,alpha_1 y_1)

for some

y_1 in mathbb{F}_q^k

and similarly

y = (y_2,alpha_2 y_2)

for some

y_2 in mathbb{F}_q^k.

Moreover since

y

is non-zero we have

y_1, y_2 ne 0.

Therefore

(y_1,alpha_1 y_1) = (y_2,alpha_2 y_2)

, then

y_1 = y_2 ne 0

and

alpha_1 y_1 = alpha_2 y_2.

This implies

alpha_1 = alpha_2

, which is a contradiction.

Any linear code having distance $<H_q^{-1}left(tfrac{1}{2}-varepsilon right) cdot 2k$ has some codeword of weight $< H_q^{-1}left(tfrac{1}{2}-varepsilon right) cdot 2k.$ Now the Lemma implies that we have at least $|P|$ different $y$ such that $wt(y) < H_q^{-1}left(tfrac{1}{2}-varepsilon right) cdot 2k$ (one such codeword $y$ for each linear code). Here $wt(y)$ denotes the weight of codeword $y$ , which is the number of non-zero positions of $y$ .

Denote

S = left { y : wt(y) < H_q^{ - 1} left (tfrac{1}{2} - varepsilon right ) cdot 2k right }

Then:

begin{align} |P| &leqslant |S| &leqslant text{Vol}_q left (H_q^{-1} left (tfrac{1}{2}-varepsilon right ) cdot 2k,2k right ) && text{Vol}_q(r,n) text{ is the volume of Hamming ball of radius } r text{ in } [q]^n &leqslant q^{H_q left (H_q^{-1}left (frac{1}{2}-varepsilon right ) right ) cdot 2k} && text{Vol}_q(pn,n) leqslant q^{H_q(p )n} &= q^{ left (frac{1}{2}-varepsilon right ) cdot 2k} &= q^{k(1-2varepsilon)} &< varepsilon(q^k-1) && text{ for } k text{ large enough } &= varepsilon N end{align}

So $|P| < varepsilon N$ , therefore the set of linear codes having the relative distance $geqslant H_q^{-1} left (tfrac{1}{2}-varepsilon right ) cdot 2k$ has at least $N - varepsilon N = (1-varepsilon)N$ elements.

Source

http://wikipedia.org/

Category:

Protocol

Wozencraft ensemble

Contents

Existence theorem

Proof

See Also on BitcoinWiki

Source