A binary code $C$ of length $n$ is said to be perfect if there exists $e \in \mathbb{N}{0}$ such that $$ {0,1}^{n}=\bigcup{u \in C} B_{e}(u)
$$
where the union is disjoint. (In words: the Hamming balls of radius $e$ about codewords are disjoint, and every binary word of length $n$ is in one of these balls.)
(a) Show that if $n$ is odd then the binary repetition code of length $n$ is perfect.
(b) Show that if $C$ is a perfect binary code of length $n$ with $e=1$ then $C$ is 1 -error correcting and $n=2^{r}-1$ for some $r \in \mathbb{N}$. Express $|C|$ in terms of $r$. [You may use any general results proved earlier in the course.]
(a) Let $n=2 m+1$. If $v$ is a binary word of length $n$ then either wt $(v) \leq m$, in which case $v$ has at most $m$ positions equal to 1 and $v \in B_{m}(00 \ldots 0)$, or $\mathrm{wt}(v) \geq m+1$ in which case $v$ has at most $m$ positions equal to 0 and $v \in B_{m}(11 \ldots 1)$. These possibilities are mutually exclusive so
$$
{0,1}^{n}=B_{m}(00 \ldots 0) \cup B_{m}(11 \ldots 1)
$$
and, taking $e=m$, we see that the binary repetition code is perfect.
(b) If $C$ is a perfect binary code with $e=1$ then then every binary word is in a unique Hamming ball of radius 1 about a codeword, and these Hamming balls are disjoint. Hence by Theorem $3.7 C$ is 1 -error correcting. marks.) Taking sizes using Lemma $7.1$ gives
$$
2^{n}=|C|\left(\left(\begin{array}{l}
n \
0
\end{array}\right)+\left(\begin{array}{l}
n \
1
\end{array}\right)\right)=|C|(1+n)
$$
Therefore $|C|=2^{n} /(n+1) .$ But we know that $|C|$ is an integer, so $n+1$ must be a power of 2 , hence $n+1=2^{r}$ for some $r \in \mathbb{N}$, and so $n=2^{r}-1$, and
$$
|C|=2^{n} /(n+1)=2^{2^{r}-1} / 2^{r}=2^{2^{r}-r-1} .
$$
(a) Use the construction in Lemma $8.12$ to find a pair of MOLS of order 3 .
(b) Use Theorem $8.13$ to write down a $(4,9,3)$ -code $C$ over ${0,1,2}$.
(c) Let $C^{\star}$ be the code with codewords obtained from $C$ by puncturing it in its final position. Write down the codewords in $C^{\star}$ and write down the length, size, and minimum distance.
(a) According to Lemma $8.12, X, Y$ are MOLS if
$$
\begin{array}{l}
X_{i j}=i+j \bmod 3 \
Y_{i j}=2 i+j \bmod 3
\end{array}
$$
So we have
$$
X=\left(\begin{array}{lll}
0 & 1 & 2 \
1 & 2 & 0 \
2 & 0 & 1
\end{array}\right), \quad Y=\left(\begin{array}{lll}
0 & 1 & 2 \
2 & 0 & 1 \
1 & 2 & 0
\end{array}\right)
$$
(b) By Theorem $8.13$ the code $C=\left{\left(i, j, X_{i j}, Y_{i j}\right) \mid 0 \leq i, j \leq q-1\right}$ code over ${0,1,2}$ if $X, Y$ are MOLS, so the codewords of $C$ are
$\begin{array}{llllllllllll}0 & 0 & 0 & 0 & 1 & 0 & 1 & 2 & 2 & 0 & 2 & 1 \ 0 & 1 & 1 & 1 & 1 & 1 & 2 & 0 & 2 & 1 & 0 & 2 \ 0 & 2 & 2 & 2 & 1 & 2 & 0 & 1 & 2 & 2 & 1 & 0\end{array}$
(c) Removing the final position in each codeword we get
$$
C^{\star}={000,011,022,101,112,120,202,210,221}
$$
So $C^{\star}$ has length 3 , size 9 and minimum distance 2 .
$(\mathbf{M T} 5461)$ Let $p$ be a prime and let $n \leq p$
(a) Show that the repetition code of length $n$ over $\mathbb{F}{p}$ is a Reed-Solomon code. (b) Show that the code consisting of all words over $\mathbb{F}{p}$ of length $n$ is a Reed-Solomon code.
(a) Take $k=1$ and evaluate polynomials at any $n$ distinct positions of your choosing. (It is fine to be definite, for example, take $a_{i}=i-1$ for $\left.1 \leq i \leq n .\right)$ Then the codewords in $R S_{p, n, 1}$ are obtained by evaluating all polynomials of degree $<1$ at the positions $a_{i} .$ Evaluating the constant polynomial $f(x)=c$ we get the codeword
$$
u(c)=(c, c, \ldots, c)
$$
So $R S_{p, n, 1}=\left\{(c, c, \ldots, c): c \in \mathbf{F}_{p}\right\}$ is the repetition code of length $n$ over $\mathbf{F}_{p}$
(b) Take $k=n$ and evaluate polynomials at $a_{i}=i-1$ for $1 \leq i \leq n$. By Lemma $2.6$ we know that $\left|R S_{p, n, n}\right|=p^{n}$. Since there are $p^{n}$ words of length $n$ it must be that $R S_{p, n, n}$ is the full set of all words of length $n$ over $\mathbf{F}_{p}$.
MT3610代写
The theory of error correcting codes
F. J. MacWilliams (Florence Jessie), 1917- N. J. A Sloane (Neil James Alexander), 1939- ProQuest (Firm)Amsterdam ; New York : North-Holland Pub. Co. ; New York : sole distributors for the U.S.A. and Canada, Elsevier/North-Holland 1977
MT4610代写
MT1820 or MT2800 ⁃ decrease a linear code into standard form, locating a parity check matrix, construction Learning outcomes:
Of a code. Hamming codes. Plotkin boundaries. Perfect codes. Hadamard codes and
Normal range and syndrome decoding tables, such as for partial construction; Check matrices, regular variety and syndrome decoding, pristine decoding. Double Code of specified length and minimal space;
Symmetric channel with given cross-over odds, without coding; Course content:
The main coding theory problem: Structure of binary codes. Rate of a
Generator and parity Q symbols (with accent (Z2) ⁃ establish and apply different bounds on the amount of possible code words within an Prerequisites: Standard concept of communicating: sayings, codes, mistakes, t-error detection and t-error
course. code. Aims: N ). Probability calculations.
⁃ utilize MOLSs and Hadamard matrices to assemble large linear codes of specific To provide an introduction into the concept of error correcting codes using the Parameters; ⁃ MT4610: Demonstrate a breadth of knowledge proper for an M-level correction. The Hamming distance in the distance Vn(q) of n-tuples within an alphabet of
Learning Outcomes: On completion of the module, students should be able to: compute the likelihood of mistake of the requirement of retransmission for a binary symmetric channel with specified cross-over likelihood, with and without coding; establish and implement many bounds on the amount of possible code words in a code of specified length and minimal space; utilize MOLSs and Hadamard matrices to build large linear codes of specific parameters; decrease a linear code into standard form, locating a parity check matrix, creating regular array and syndrome decoding tables, such as for semi decoding. The student will demonstrate a breadth of knowledge suitable to get an M-level course. 120 hours of personal research, such as work on issue sheets and examination preparation. This might include discussions with the course leader if the student wants. 001.539 HIL Coding Theory — an Initial Course – S Ling and C Xing (Cambridge UP 2004) 001.539 LIN Formative Assessment & Feedback: Formative missions in the kind of 8 issue sheets. The students will get comments as written opinions on their efforts. Summative Assessment: Assessment (%) A two-hour written examination: 85% Coursework (percent ) Establish exercises. 15 percent
At the completion of the Program, pupils should be able to: ⁃ compute the probability of mistake of the requirement of retransmission to get a binary
MT5461代写
MT1820 or MT2800 ⁃ reduce a linear code to standard form, locating a parity check matrix, building Learning outcomes:
Of a code. Hamming codes. Plotkin boundaries. Puncturing a code. Perfect codes. Hadamard codes and
Standard array and syndrome decoding tables, including for partial decoding; Check matrices, standard array and syndrome decoding, incomplete decoding. Double Code of given length and minimal distance;
Symmetric channel with given cross-over probability, without coding; Course content:
The main coding theory problem: Structure of binary codes. Rate of a
Linear Codes: Linear codes as linear subspaces of V(nq). Generator and parity Q symbols (with emphasis on (Z2) ⁃ establish and apply various bounds on the amount of possible code words in a Prerequisites: Standard concept of coding: Words, codes, errors, t-error detection and t-error
course. code. Equivalence of codes. The Hamming, Singleton, Gilbert-Varshamov and Aims: N). Probability calculations.
⁃ use MOLSs and Hadamard matrices to assemble large linear codes of specific To provide an introduction into the theory of error correcting codes employing the Parameters; ⁃ MT4610: Demonstrate a breadth of understanding appropriate for an M-level correction. The Hamming distance in the space Vn(q) of n-tuples within an alphabet of
Course Code: MT4610 Course Value: 15 credits Status: (ie:Core, or Optional) Optional Course Title: Error-Correcting Codes Availability: (state which teaching terms) Term 2 Requirements: MT1820 or MT2800 Recommended: None Co-ordinator: Course Staff: Learning Objectives: To give an introduction into the concept of error correcting codes using the methods of elementary enumeration, linear algebra and finite fields. Learning Outcomes: On completion of the module, students should be able to: compute the probability of error of the requirement of retransmission for a binary symmetric channel with given cross-over probability, with and without coding; prove and apply various bounds on the number of possible code words in a code of specified length and minimal space; utilize MOLSs and Hadamard matrices to build large linear codes of specific parameters; reduce a linear code to standard form, finding a parity check matrix, creating standard array and syndrome decoding tables, such as for semi decoding. The student will demonstrate a breadth of knowledge suitable to get an M-level course. 120 hours of personal study, including work on issue sheets and examination preparation. This might include discussions with the course leader if the student wishes. Key Bibliography: A First Course in Coding Theory – R Hill (OUP). 001.539 HIL Coding Theory — an Initial Course – S Ling and C Xing (Cambridge UP 2004) 001.539 LIN Formative Assessment & Feedback: Formative missions in the kind of 8 problem sheets. The students will receive feedback as written comments on their efforts. Summative Assessment: Assessment (%) A two-hour written examination: 85% Coursework (percent ) Set exercises. 15 percent
At the completion of the course, students should be able to: Levenshtein’s theorem. Codes based on mutually orthogonal latin squares (MOLS). ⁃ compute the probability of mistake of the requirement of retransmission to get a binary
Error Correcting Codes代写
Nollan
Basic idea: add redundant bits
Code Rate: Proportion of data-stream that is useful Denoted as Code(n, k), $\mathrm{n}>\mathrm{k}$, generates $\mathrm{n}$ bits for every $\mathrm{k}$ bits Code Rate $=\mathrm{k} / \mathrm{n}$
Error Detection Vs Error Correction
How much errors can be corrected? Shannon Limit 1948 :
The theoretical maximum information transfer rate of the channel
Shannon theorem: “Given a noisy channel with channel capacity C and information transmitted at a rate $\mathrm{R}$, then if $\mathrm{R}<\mathrm{C}$ there exist codes that allow the probability of error at the receiver to be made arbitrarily small”
