Введение в алгебраическую теорию кодирования

Найдите вес Хэмминга каждого кодового слова из таблицы 29.1 (кодовых слов кода Хэмминга $(7,4)$ из примера 1):

Найдите расстояние Хэмминга между следующими парами векторов: $\left\{ 1101, 0111\right\}$, $\left\{ 0220, 1122\right\}$, $\left\{ 11101, 00111\right\}$.

Обращаясь к примеру 1, используйте метод ближайшего соседа для декодирования принятых слов $0000110$ и $1110100$.

Для любого векторного пространства $V$ и любых $u, v, w$ из $F^n$ докажите, что расстояние Хэмминга обладает следующими свойствами.

Определите двоичный линейный код $(6, 3)$ с порождающей матрицей

Покажите, что для двоичных векторов $\operatorname {wt}(u + v) \ge \operatorname {wt}(u) = \operatorname {wt}(v)$, причём равенство имеет место тогда и только тогда, когда для всех $i$ $i$-я компонента $u$ равна $1$, если $i$-я компонента $v$ равна $1$.

Если минимальный вес любого ненулевого кодового слова равен $2$, что можно сказать о способности кода обнаруживать ошибки?

Пусть $C$ --- линейный код с весом Хэмминга $3$, а $C'$ --- код с весом Хэмминга $4$. Что может делать $C'$, чего не может $C$?

Пусть $C$ --- двоичный линейный код. Покажите, что кодовые слова чётного веса образуют подкод $C$. (Подкодом кода называется подмножество кода, само являющееся кодом.)

Пусть

Какова способность $C$ исправлять ошибки? Какова способность $C$ обнаруживать ошибки?

Пусть проверочная матрица двоичного линейного кода имеет вид

Может ли код исправлять любую одиночную ошибку?

Используйте порождающую матрицу

для построения троичного линейного кода $(4, 2)$. Какова проверочная матрица этого кода? Какова способность этого кода исправлять ошибки? Какова его способность обнаруживать ошибки? Используйте декодирование по проверочной матрице для декодирования принятого слова $1201$.

Найдите все кодовые слова двоичного линейного кода $(7, 4)$, порождающая матрица которого равна

Найдите проверочную матрицу этого кода. Будет ли этот код исправлять любую одиночную ошибку?

Покажите, что в двоичном линейном коде либо все кодовые слова оканчиваются на $0$, либо ровно половина из них оканчивается на $0$. Что можно сказать о других компонентах?

Пусть кодовое слово $v$ принято в виде вектора $u$. Покажите, что декодирование по смежным классам декодирует $u$ как кодовое слово $v$ тогда и только тогда, когда $u - v$ является лидером смежного класса.

Рассмотрите двоичный линейный код

Постройте стандартный массив для $C$. Используйте декодирование ближайшего соседа для декодирования $11101$ и $01100$. Если принятое слово $11101$ содержит ровно одну ошибку, можем ли мы определить предполагаемое кодовое слово? Если принятое слово $01100$ содержит ровно одну ошибку, можем ли мы определить предполагаемое кодовое слово?

Постройте двоичный линейный код $(6, 3)$ с порождающей матрицей

Декодируйте каждое из принятых слов

следующими методами:

Пусть минимальный вес любого ненулевого кодового слова линейного кода равен $6$. Обсудите возможные варианты исправления и обнаружения ошибок.

Используя код и проверочную матрицу из примера 10, покажите, что декодирование по проверочной матрице не может обнаружить никакие кратные ошибки (то есть две или более ошибок).

Пусть последняя строка стандартного массива для двоичного линейного кода имеет вид

Определите код.

Сколько кодовых слов имеется в троичном линейном коде $(6, 4)$? Сколько возможных принятых слов имеется для этого кода?

Если проверочная матрица двоичного линейного кода равна

будет ли код исправлять любую одиночную ошибку? Почему?

Пусть проверочная матрица троичного кода равна

Может ли код исправлять все одиночные ошибки? Обоснуйте свой ответ.

Докажите, что для декодирования ближайшего соседа верно обратное утверждение теоремы 29.2.

Может ли двоичный линейный код $(6, 3)$ исправлять двойные ошибки методом ближайшего соседа? Не предполагайте, что код систематический.

Докажите, что не существует стандартной порождающей матрицы $G$ размера $2 \times 5$, которая порождает линейный код $(5, 2)$ над $\mathbb {Z}_3$, способный обнаруживать все возможные тройные ошибки.

Почему метод ближайшего соседа с двоичным линейным кодом $(4, 2)$ не может исправлять все одиночные ошибки?

Пусть одна строка стандартного массива для двоичного кода имеет вид

Определите строку, содержащую $100001$.

Используйте поле $F = \mathbb {Z}_2[x]/ \left\langle x^2 + x + 1\right\rangle$ для построения линейного кода $(5, 2)$, который исправляет любую одиночную ошибку.

Найдите стандартную порождающую матрицу линейного кода $(4, 2)$ над $\mathbb {Z}_3$, который кодирует $20$ как $2012$, а $11$ как $1100$. Определите весь код и проверочную матрицу кода. Будет ли код исправлять все одиночные ошибки?

Предположим, что $C$ --- двоичный линейный код $(n, k)$ и что для каждой позиции $i = 1, 2, \ldots , n$ код $C$ содержит хотя бы один вектор с $1$ на $i$-й позиции. Покажите, что средний вес кодового слова равен $n/2$.

Пусть $C$ --- линейный код $(n, k)$ над $F$ такой, что минимальный вес любого ненулевого кодового слова равен $2t + 1$. Покажите, что не каждый вектор веса $t+1$ из $F^n$ может быть лидером смежного класса.

Пусть $C$ --- двоичный линейный код $(n, k)$ над $F = \mathbb {Z}_2$. Если $v \in F^n$, но $v \notin C$, покажите, что $C \cup (v + C)$ является линейным кодом.

Пусть $C$ --- двоичный линейный код. Покажите, что либо каждый элемент $C$ имеет чётный вес, либо ровно половина элементов $C$ имеет чётный вес. (Сравните с упражнением 27 главы 5.)

Пусть $C$ --- линейный код $(n, k)$. Для каждого $i$, $1 \le i \le n$, положим

. Покажите, что $C_i$ является подкодом $C$.