Basic

Codes

  • \([m, n , \delta]\) code:
  • \(Enc(\text{message})\): Encode a message of size \(n\) to a codeword of size \(m\).
  • \(\delta\) is the minimum distance (Hamming) between any two codewords.
  • Hamming distance is the number of different location between two codewords.
  • The alphabet of this code can be binary or a finite field.
  • Rate: \(\frac{n}{m}\) and Relative distance: \(\frac{\delta}{m}\)

Vandermonde matrix

  • A matrix \(G \in F^{m \times n}\) (\(m\) rows and \(n\) columns). with the elements \(G_{ij} = \alpha_i^{j-1}\). So:
\[G = \begin{bmatrix} 1 & \alpha_1 & \alpha_1^2 & \dots & \alpha_1^{n-1} \\ 1 & \alpha_2 & \alpha_2^2 & \dots & \alpha_2^{n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \alpha_m & \alpha_m^2 & \dots & \alpha_m^{n-1} \end{bmatrix}_{m\times n} \]
  • A Vandermonde matrix is ​​therefore completely determined by the numbers \(\alpha_{i}(i=1,2,\ldots ,m)\).

Polynomial evaluation

  • Consider polynomial \(p(x) = p_nx^n + p_{n-1}x^{n-1}+\dots + p_0\), then we can use Vandermonde matrix for evaluating \(p(x)\) in a number of points \(r_0, r_1, \dots, r_m\).
  • First define the Vandermonde matrix of \(r_0, r_1, \dots, r_m\):
\[G = \begin{bmatrix} 1 & r_0 & r_0^2 & \dots & r_0^{n} \\ 1 & r_1 & r_1^2 & \dots & r_1^{n} \\ 1 & r_2 & r_2^2 & \dots & r_2^{n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & r_m & r_m^2 & \dots & r_m^{n} \end{bmatrix}_{(m+1) \times (n+1)} \]
  • Then multiply \(G\) by the vector \(p = (p_0, p_1, \dots,p_n)\):
\[G.p = \begin{bmatrix} 1 & r_0 & r_0^2 & \dots & r_0^{n} \\ 1 & r_1 & r_1^2 & \dots & r_1^{n} \\ 1 & r_2 & r_2^2 & \dots & r_2^{n} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & r_m & r_m^2 & \dots & r_m^{n} \end{bmatrix} \begin{bmatrix} p_0 \\ p_1 \\ p_2 \\ \cdots \\ p_n \end{bmatrix} = \begin{bmatrix} \displaystyle\sum_{i=0}^n {p_{i}r_0^{i}} \\ \displaystyle\sum_{i=0}^n {p_{i}r_1^{i}} \\ \vdots \\ \displaystyle\sum_{i=0}^n {p_{i}r_m^{i}} \\ \end{bmatrix} \]
  • It is obvious the last vector is evaluation \(p(x)\) on \(r_0, r_1, \dots, r_m\)

Linear codes

  • Matrix \(G \in F^{m \times n}\)
  • Message \(x \in F^{n}\) (\(n\)-vector over the field \(F\))
  • Then \(Gx\) is the encoded of message \(x\) and called codeword. The length of \(Gx\) is \(m\) (\(Gx \in F^m\)).
  • \(n\) is the message length.
  • \(m\) is the block length.

Distance of code

  • \(\delta = \min\limits_{x\in F^n\text{\textbackslash} \{0\}} \Vert Gx \Vert_0\). where \(\Vert Gx \Vert_0\) denotes the number of nonzero entries in \(Gx \in F^m\).
  • \(x, y \in F^n\) with \(x \not = y\). They will differ in at least \(d\) places after being encoded.
\[\Vert Gx - Gy \Vert_0 = \Vert G(x-y) \Vert_0 \geqslant d, \]

since \(x-y \not = 0\).

Reed–Solomon codes

  • Are codes with some extra properties as below:
    • Pick any subset of evaluation points S = \(\{\alpha_1, \dots, \alpha_m\} \subseteq F\)
    • The Matrix \(G\) should be exactly the Vandermonde matrix.
  • We want to generate \(Gx\) in definition of linear codes with Reed–Solomon definition:
    • Based on Reed–Solomon: \(G \in F^{m×n}\) and \(G_{ij} = α_{i}^{j−1}\)
    • \(Gx\) is the encoded message \(x\), and called codeword.
    \[Gx = \begin{bmatrix} 1 & \alpha_1 & \alpha_1^2 & \dots & \alpha_1^{n-1} \\ 1 & \alpha_2 & \alpha_2^2 & \dots & \alpha_2^{n-1} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \alpha_m & \alpha_m^2 & \dots & \alpha_m^{n-1} \end{bmatrix}_{m\times n} \begin{bmatrix} x_1 \\ x_2 \\ \cdots \\ x_n \end{bmatrix} = \begin{bmatrix} \displaystyle\sum_{j=1}^n {x_{j} \alpha_1^{j-1}} \\ \vdots \\ \displaystyle\sum_{j=1}^n {x_{j} \alpha_m^{j-1}} \end{bmatrix} \]
    • So, \((Gx)_i = \displaystyle\sum_{j=1}^n {x_{j} \alpha_i^{j-1}}\) is a degree at most \(n-1\) polynomial with coefficients \(x_j\), evaluated at each of the \(\alpha_i\)
    • So, this polynomial has at most \(n-1\) roots.
    • Then the distance of this code is at least m − n + 1 since. (0x6980 uderestanding: Because we can create a polynomial where \(\alpha_1, \dots, \alpha_{n-1}\) are the roots, we then use the coefficients of this polynomial instead of \(x_j\). By doing so, we make an \(x\) such that \(m-n+1\) of the coordinates of \(Gx\) are zero.)
    • we can construct a polynomial of degree \(n-1\) which has exactly \(m-n+1\) zeros when evaluated over the points \(\alpha_1,\dots, \alpha_m\), which makes the distance of this code exactly equal to \(m-n+1\).(0x6980?!)

Important

  • Choosing the elements \(m, n, S, F, \delta\) can influence the formation of different codes.

Binary additive RS code

The collection of codes \(RS[F; S; ρ]\) where \(F\) is a binary field and \(S\) an additive coset.

Reed-Solomon (RS)

  • The code \(RS[F; S; ρ]\) is the space of functions \(f : S \rightarrow F\) that are evaluations of polynomials of degree \(d < ρN\)
  • \(S\) is an evaluation set of \(N\) elements in a finite field \(F\).
  • rate parameter \(ρ \in ( 0; 1\rbrack\).

RS proximity problem

  • The verifier has oracle access to \(f : S \rightarrow F\).
  • Problem: Is the verifier able with “large” confidence and “small” query complexity, determine that:
    1. \(f\) is a codeword of RS[F; S; ρ] Or
    2. \(f\) is \(\delta\)-far from all codewords. (Hamming distance)

RS proximity testing

  • When no additional data is provided to the verifier, the RS proximity problem is commonly called a testing problem.
  • \(d + 1\) queries are necessary and sufficient to solve the problem.
    • codewords are accepted by their tester with probability 1 whereas
    • functions that are δ-far from the code rejected with probability ≥ δ.

Binary field

The finite field \(F_q\) is binary field if \(q = 2^m, \space m \in \mathbb{N}\).

Additive Coset

  • \(H\) is subgroup of group \((G, +)\).
  • \(g \in G\).
  • The left and right coset of \(H\) in \(G\) are
\[\tag{left coset} g + H = \{g + h \space | \space h \in H\} \] \[\tag{right coset} H + g = \{h + g \space | \space h \in H\} \]
  • If G is commutative group then \(\forall H,\space \forall g \in G; \space\space g + H = H + g\).
IntroFast Fourier Transform