# Глава 5, Пакулев Александр M3435

### 1. Постройте циклические коды длин 𝑛 = 3, ..., 9. Определите скорость и минимальное расстояние кодов и дуальных к ним кодов
- $n = 3$
$x^3 - 1 = (x + 1)(x^2 + x + 1)$
$g(x) = x^2 + x + 1$

$(3, 1)$ код
Cкорость $1/3$
$$G=\begin{pmatrix} 1&1&1 \end{pmatrix}$$

$d=3$

Дуальный код $h(x) = {x^3 + 1\over x^2 + x + 1} = x + 1$
$$H=\begin{pmatrix} 1&1&0\\ 0&1&1 \end{pmatrix}$$

- $n = 4$
$x^4 + 1 = (x^2 + 1)(x + 1)(x + 1)$
$g(x) = x^2 + 1$

$(4, 2)$ код
Скорость $1/2$

$$G=\begin{pmatrix} 1&0&1&0\\ 0&1&0&1 \end{pmatrix}
$$

$d = 2$

Дуальный код $h(x) = {x^4 + 1\over x^2 + 1} = x^2 + 1$
$$H=\begin{pmatrix} 1&0&1&0\\ 0&1&0&1 \end{pmatrix}$$

- $n = 5$
$x^5 + 1 = (x + 1)(x^4 + x^3 + x^2 + x + 1)$
$g(x) = x^4 + x^3 + x^2 + x + 1$

$(5, 1)$ код
Скорость $1/5$

$$G=\begin{pmatrix} 1&1&1&1&1 \end{pmatrix}$$

$d=5$

Дуальный код $h(x) = {x^5 + 1\over x^4 + x^3 + x^2 + x + 1} = x + 1$
$$H=\begin{pmatrix} 1&1&0&0&0\\ 0&1&1&0&0\\ 0&0&1&1&0\\ 0&0&0&1&1 \end{pmatrix}$$

- $n = 6$
$x^6 + 1 = (x + 1)(x^2 + x + 1)(x + 1)(x^2 + x + 1)$
$g(x) = x^2 + x + 1$

$(6, 4)$ код
Скорость $2/3$

$$G=\begin{pmatrix} 1&1&1&0&0&0\\ 0&1&1&1&0&0\\ 0&0&1&1&1&0\\ 0&0&0&1&1&1 \end{pmatrix}$$

$d=2$

Дуальный код $h(x) = {x^6 + 1\over x^2 + x + 1} = x^4 + x^3 + x + 1$
$$H=\begin{pmatrix} 1&1&0&1&1&0&0\\ 0&1&1&0&1&1&0\\ 0&0&1&1&0&1&1 \end{pmatrix}$$

- $n = 7$
$x^7 + 1 = (x + 1)(x^3 + x + 1)(x^3 + x^2 + 1)$
$g(x) = x^3 + x + 1$

$(7, 4)$ код
Скорость $4/7$

$$G=\begin{pmatrix} 1&1&0&1&0&0&0\\ 0&1&1&0&1&0&0\\ 0&0&1&1&0&1&0\\ 0&0&0&1&1&0&1\\ \end{pmatrix}$$

$d=3$

Дуальный код $h(x) = {x^7 + 1\over x^2 + x + 1} = x^4 + x^3 + x + 1$
$$H=\begin{pmatrix} 1&1&0&1&1&0&0\\ 0&1&1&0&1&1&0\\ 0&0&1&1&0&1&1 \end{pmatrix}$$

- $n = 8$
$x^8 + 1 = (x + 1)^8$
$g(x) = (x + 1)^3 = x^3 + x^2 + x + 1$

$(8, 5)$ код
Скорость $5/8$

$$G=\begin{pmatrix} 1&1&1&1&0&0&0\\ 0&1&1&1&1&0&0\\ 0&0&1&1&1&1&0\\ 0&0&0&1&1&1&1 \end{pmatrix}$$

$d=2$

Дуальный код $h(x) = {x^8 + 1\over (x + 1)^3} = (x + 1)^5$
$$H=\begin{pmatrix} 1&1&1&1&1&1&0\\ 0&1&1&1&1&1&1 \end{pmatrix}$$

- $n = 9$
$x^9 + 1 = (x + 1)(x^2 + x + 1)(x^6 + x^3 + 1)$
$g(x) = x^2 + x + 1$

$(9, 7)$ код
Скорость $7/9$

$$G=\begin{pmatrix} 1&1&1&0&0&0&0&0\\ 0&1&1&1&0&0&0&0\\ 0&0&1&1&1&0&0&0\\ 0&0&0&1&1&1&0&0\\ 0&0&0&0&1&1&1&0\\ 0&0&0&0&0&1&1&1 \end{pmatrix}$$

$d=2$

Дуальный код $h(x) = {x^9 + 1\over x^2 + x + 1} = x^7 + x^6 + x^4 + x^3 + x + 1$
$$H=\begin{pmatrix} 1&1&0&1&1&0&1&1&0\\ 0&1&1&0&1&1&0&1&1 \end{pmatrix}$$

### 2. Постройте все поля характеристики 2 из 8 элементов. Проверьте, что они изоморфны друг другу.
- Порождающий многочлен $g(x) = x^3 + x^2 + 1$

| Степень | Полиномиальное представление | Двоичная запись полинома |
|:---------:| :----------------------------: | :------------------------: |
| $-\infty$ | $0$ | 000 |
| 0 | $1$ | 001 |
| 1 | $x$ | 010 |
| 2 | $x^2$ | 100 |
| 3 | $x^2 + 1$ | 101 |
| 4 | $x^2 + x + 1$ | 111 |
| 5 | $x + 1$ | 011 |
| 6 | $x^2 + x$ | 110 |

- Порождающий многочлен $g(x) = x^3 + x + 1$

| Степень | Полиномиальное представление | Двоичная запись полинома |
|:---------:| :----------------------------: | :------------------------: |
|$-\infty$| $0$| 000|
|0| $1$ |001|
|1| $x$ |010|
|2| $x^2$ |100|
|3| $x + 1$ |011|
|4| $x^2 + x$ |110|
|5| $x^2 + x + 1$ |111|
|6| $x^2 + 1$ |101|

### 3. Определите порядки элементов мультипликативной группы поля $GF(q)$ при $q = 2, 3, 4, 5, 7, 8, 9$.

- $q = 2$
Порядки -- $1$
- $q = 3$
Порядки -- $1, 2$
- $q = 4$
Порядки -- $1, 3$
- $q = 5$
Порядки -- $1, 2, 4$
- $q = 6$
6 не простое и не степень простого числа
- $q = 7$
Порядки -- $1, 2, 3, 6$
- $q = 8$
Порядки -- $1, 7$
- $q = 9$
Порядки -- $1, 2, 4, 8$

### 4. Постройте поле $GF(2^4)$ как кольцо вычетов по модулю $p(x) = 1 + x + x^4$. Найдите обратные элементы к элементам поля.

| Степень | Полиномиальное представление | Обратный элемент | Двоичная запись полинома |
|:---------:| :----------------------------: | :------------------------: | :-----: |
|$-\infty$ |$0$ | |0000|
|0 |$1 |$1$| 0001|
|1 |$x^1 |$1 + x^3$| 0010|
|2 |$x^2 |$1 + x^2 + x^3$| 0100|
|3 |$x^3 |$1 + x^1 + x^2 + x^3$ |1000|
|4 |$1 + x^1$| $x^1 + x^2 + x^3$| 0011|
|5 |$x^1 + x^2$| $1 + x^1 + x^2$ |0110|
|6 |$x^2 + x^3$| $x^1 + x^3$|1100|
|7 |$1 + x^1 + x^3$| $1 + x^2$| 0101|
|8 |$1 + x^2$| $1 + x^1 + x^3$| 1011|
|9 |$x^1 + x^3$| $x^2 + x^3$| 1100|
|10| $1 + x^1 + x^2$| $x^1 + x^2$| 0110|
|11| $x^1 + x^2 + x^3$| $1 + x^1$| 1110|
|12| $1 + x^1 + x^2 + x^3$| $x^3$| 1111|
|13| $1 + x^2 + x^3$| $x^2$| 1101|
|14| $1 + x^3$ |$x^1$| 1001|

### 5. Постройте поле $GF(2^4)$ как кольцо вычетов по модулю $p(x) = 1 + x + x^2 + x^3 + x^4$. Найдите обратные элементы к элементам поля.
| Степень | Полиномиальное представление | Обратный элемент | Двоичная запись полинома |
|:---------:| :----------------------------: | :------------------------: | :-----: |
|$-\infty$| $0$| |0000|
|0 |$1$ |$1$|0001|
|1 |$x^1$ |$1 + x^1 + x^2 + x^3$|0010|
|2 |$x^2$ |$x^3$|0100|
|3 |$x^3$ |$x^2$|1000|
|4 |$1 + x^1 + x^2 + x^3$ |$x^1$|1111|
|5 |$1$ |$1$|0001|

При примитивном элементе $x$ есть повторяющиеся элементы. Возьмем приметивный элемент $x + 1$.

| Степень | Полиномиальное представление | Обратный элемент | Двоичная запись полинома |
|:----------:| :-----------------------------: | :--------------------------: | :-----: |
|$-\infty$| $0$||0000|
|0| $1$ |$1$ |0001|
|1| $1 + x^1$ |$x^1 + x^3$ |0010|
|2| $1 + x^2$ |$x^1 + x^2$ |0100|
|3| $1 + x^1 + x^2 + x^3$ |$x^1$ |1000|
|4| $x^1 + x^2 + x^3$ |$1 + x^1 + x^3$ |1110|
|5| $1 + x^2 + x^3$ |$x^2 + x^3$ |1101|
|6| $x^3$ |$x^2$ |1000|
|7| $1 + x^1 + x^2$ |$1 + x^3$ |0111|
|8| $1 + x^3$ |$1 + x^1 + x^2$ |1001|
|9| $x^2$ |$x^3$ |0100|
|10| $x^2 + x^3$ |$1 + x^2 + x^3$ |1100|
|11| $1 + x^1 + x^3$ |$x^1 + x^2 + x^3$ |1011|
|12| $x^1$ |$1 + x^1 + x^2 + x^3$|0010|
|13| $x^1 + x^2$ |$1 + x^2$ |0110|
|14| $x^1 + x^3$ |$1 + x^1$ |1010|