Пример 1

При использовании линейного помехоустойчивого кода Хэмминга H(7,4) над двоичным алфавитом с проверочной матрицей \[H = \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ \end{pmatrix},\] получено кодовое слово r=0101101.

Была ли ошибка при передаче?

Каково наиболее вероятное отправленное кодовое слово?

Каково исходное сообщение?

Вычислим синдром \(s = Hr \mod 2\) \[s = \begin{pmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ \end{pmatrix} \begin{pmatrix} 0 \\ 1 \\ 0 \\ 1 \\ 1 \\ 0 \\ 1 \end{pmatrix}\] \[s = \begin{pmatrix}1 \\ 0 \\ 0\end{pmatrix}.\]

Поскольку для разрешённых кодовых слов \(s=Hx = 0\), а вычисленный вектор синдрома не равен нулю, произошла ошибка передачи.

Код (7,4) имеет 4 информационных и 3 проверочных бита. Всего он таким образом имеет \(2^4 = 16\) разрешённых кодовых слов и \(2^3=8\) возможных значений синдрома. Учитывая, что одно (нулевое) значение синдрома означает отсутствие ошибок, для индикации ошибки имеется 7 различных вариантов. Этого достаточно для того, чтобы обнаружить ошибку в одном бите.

Поскольку \(Hr = Hx + He = He\), вектор синдрома зависит только от вектора ошибки. Построим таблицу синдромов для всех возможных векторов одной ошибки:

Вычисленный синдром 100 соответствует ошибке в 4-м бите. Соответственно, наиболее вероятное отправленное кодовое слово \(x = 0100101\). Убедимся, что его синдром равен 0: \[s = 010 + 101 + 111 = 000 \mod 2\]

Поскольку код является кодом Хэмминга, матрицу H можно единственным образом привести к стандартному виду перестановкой столбцов, и тогда сообщение записано в битах, соответствующих неединичным столбцам проверочной матрицы, т.е. в битах 3, 5, 6, 7. m = 0101.

Пример 2

При использовании линейного помехоустойчивого кода H(7,3) над двоичным алфавитом с проверочной матрицей \[H = \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},\] получено кодовое слово r=1100111.

Считать, что порождающая матрица в стандартном виде.

Была ли ошибка при передаче?

Каково наиболее вероятное отправленное кодовое слово?

Каково исходное сообщение?

Вычислим вектор синдрома: \[s = (0001)^\mathrm T\]

Вектор синдрома не равен 0.

Код имеет 3 информационных и 4 проверочных бита, соответственно имеет 8 разрешённых кодовых слов и 16 различных синдромов, то есть может различать 16 различных векторов ошибки.

Вектор синдрома соответствует единичной ошибке в последнем бите.

Наиболее вероятное кодовое слово 1100110.

Поскольку мы считаем, что порождающая матрица в стандартном виде, мы автоматически знаем, что первые 3 (старших) бита должны быть информационными, и тогда сообщение \(m=110\).

Тем не менее, проверим, что соответствующая данной проверочной матрице порождающая матрица, имеющая стандартны вид, существует.

Разрешённые кодовые слова (из решения Hx = 0):

• 0000000
• 1001100
• 0101010
• 1100110
• 0011001
• 1010101
• 0110011
• 1111111

Следует отметить, что кодовое расстояние = 3, и код способен гарантированно исправить не более 1 ошибки.

Порождающая матрица может быть образована, вообще говоря, любой комбинацией из 3 разрешённых кодовых слов, кроме 0000000 и 1111111, но мы ищем стандартный вариант – когда в левой части находится единичная матрица. Тогда единственная возможная порождающая матрица

\[G = \begin{pmatrix} 1&0&0&1&1&0&0 \\ 0&1&0&1&0&1&0 \\ 0&0&1&1&0&0&1 \\ \end{pmatrix},\]

то есть сообщение повторяется в первых (старших) трёх и последних (младших) трёх битах, а “средний” бит является битом чётности.

Отметим, что эквивалентная систематическая проверочная матрица для данной порождающей имеет вид

\[H = \begin{pmatrix} 1 & 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 1 \\ \end{pmatrix}\]

Она может быть получена из исходной линейными операциями над строками.

Пример 3

При использовании линейного помехоустойчивого кода H(6,3) над двоичным алфавитом с проверочной матрицей \[H = \begin{pmatrix} 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 1 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 \\ \end{pmatrix},\] получено кодовое слово r=111000.

Считать, что порождающая матрица в стандартном виде.

Была ли ошибка при передаче?

Каково наиболее вероятное отправленное кодовое слово?

Каково исходное сообщение?

Синдром 010 соответствует единичной ошибке в предпоследнем бите. Наиболее вероятное кодовое слово x = 111010.

Поскольку порождающая матрица в стандартном виде, m = 111.

Код имеет 3 информационных и 3 проверочных символа. Всего он может теоретически различать 8 ошибок. Разрешённые кодовые слова (8):

• 000000
• 011100
• 111010
• 100110
• 110001
• 101101
• 001011
• 010111

Кодовое расстояние 3, соответственно код гарантированно способен обнаружить ошибку кратности 1.

Систематическая порождающая матрица

\[G = \begin{pmatrix} 1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ \end{pmatrix}\]

Соответствующая систематическая проверочная матрица

\[H' = \begin{pmatrix} 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 \\ \end{pmatrix}\]

Она может быть получена из исходной линейными операциями над строками.

Пример 4

При использовании циклического кода (7, 4) с порождающим многочленом \(g(x) = x^3+x+1\) и правилом построения кодов \(c(x) = m(x)\cdot g(x)\) получено кодовое слово r = 0010000

Была ли ошибка при передаче?

Каково наиболее вероятное отправленное кодовое слово?

Каково исходное сообщение?

Многочлен, соответствующий сообщению \(r(x) = x^4\).

Синдром \(s(x) = \mathrm{rem}(r(x), g(x))\) (остаток от деления r(x) на g(x))

Разделим \(x^4\) на \(x^3+x+1\). Результат \(x\). Остаток тогда \(x^4 - x(x^3+x+1) = x^2+x\) (все операции в поле \(GF(2)\), поэтому \(-1 = 1\))

Произошла ошибка передачи. Поскольку синдром зависит только от ошибки, данный синдром соответствует ошибке в единичном бите. То есть, исходное кодовое слово \(x = 0000000\), и исходное сообщение \(m = 0000\).

Пример 5

При использовании циклического кода (6, 3) с порождающим многочленом \(g(x) = x^3+1\) и правилом построения кодов \(c(x) = m(x)\cdot g(x)\) получено кодовое слово r = 001001

Была ли ошибка при передаче?

Каково наиболее вероятное отправленное кодовое слово?

Каково исходное сообщение?

Многочлен, соответствующий сообщению \(r(x) = x^3 + 1\).

Синдром \(s(x) = \mathrm{rem}(r(x), g(x)) = 0\)

Ошибки передачи вероятно не было, наиболее вероятное сообщение r = 001001

Исходное сообщение есть результат деления \(r(x)\) на \(g(x)\), т.е. \(m(x) = r(x)/g(x) = 1\). Исходное сообщение таким образом \(m = 001\).

Пример 6

При использовании циклического кода (6, 3) с порождающим многочленом \(g(x) = x^3+x+1\) и правилом построения кодов \(c(x) = m(x)\cdot g(x)\) получено кодовое слово r = 001001

Была ли ошибка при передаче?

Каково наиболее вероятное отправленное кодовое слово?

Каково исходное сообщение?

Многочлен, соответствующий сообщению \(r(x) = x^3 + 1\).

Синдром \(s(x) = \mathrm{rem}(r(x), g(x)) = x\), s = 010

Произошла ошибка передачи. Предположим, что это единичная ошибка. Тогда, \[s(x) = \mathrm{rem}(e(x), g(x)) = \mathrm{rem}(x^i, g(x)),\] где \(i\) – номер ошибочного бита (от 0 – младший до 5 – старший). Понятно, что \(i=1\), т.е. синдром соответствует ошибке в предпоследнем бите.

Наиболее вероятное кодовое слово c = 001011, \(c(x) = x^3+x+1\).

Исходное сообщение есть результат деления \(c(x)\) на \(g(x)\), т.е. \(m(x) = c(x)/g(x) = 1\). Исходное сообщение таким образом m = 001.

Пример 7

При использовании циклического кода (6, 3) с порождающим многочленом \(g(x) = x^3+x+1\) и систематическим правилом построения кодов, получено кодовое слово r = 000111

Была ли ошибка при передаче?

Каково наиболее вероятное отправленное кодовое слово?

Каково исходное сообщение?

Многочлен, соответствующий сообщению \(r(x) = x^2 + x + 1\).

Синдром \(s(x) = \mathrm{rem}(r(x), g(x)) = x^2 + x + 1\), s = 111

Произошла ошибка передачи. Предположим, что это единичная ошибка. Тогда, \[s(x) = \mathrm{rem}(e(x), g(x)) = \mathrm{rem}(x^i, g(x)),\] где \(i\) – номер ошибочного бита (от 0 – младший до 5 – старший). Понятно, что \(i>3\) (для \(i<3\), \(s(x)=x^i\), для \(i=3\), \(s(x) = x+1\)). \[\mathrm{rem}(x^4, g(x)) = x^2+x,\] \[\mathrm{rem}(x^5, g(x)) = x^2+x+1,\] \(i=5\), значит ошибка произошла в старшем бите.

Наиболее вероятное кодовое слово c = 100111, \(c(x) = x^3+x+1\).

Поскольку код построен систематически, первые (левые) \(k=n-r = 3\) бит являются исходным сообщением. \(m=100\)

Пример 8

При использовании циклического кода (6, 3) с порождающим многочленом \(g(x) = x^3+x^2+1\) и правилом построения кодов \(c(x)=m(x)g(x)\), получено кодовое слово r = 011000

Была ли ошибка при передаче?

Каково наиболее вероятное отправленное кодовое слово?

Каково исходное сообщение?

Многочлен, соответствующий сообщению \(r(x) = x^4 + x^3\).

Синдром \(s(x) = \mathrm{rem}(r(x), g(x)) = x\), s = 010

Произошла ошибка передачи. Синдром соответствует ошибке во втором справа бите.

Наиболее вероятное кодовое слово c = 011010, \(c(x) = x^4 + x^3 + x\).

Исходное сообщение есть результат деления \(c(x)\) на \(g(x)\), т.е. \(m(x) = c(x)/g(x) = x\). Исходное сообщение таким образом m = 010.

Пример 9

При использовании циклического кода (6, 3) с порождающим многочленом \(g(x) = x^3+x^2+1\) и систематическим правилом построения кодов, получено кодовое слово r = 011000

Была ли ошибка при передаче?

Каково наиболее вероятное отправленное кодовое слово?

Каково исходное сообщение?

Многочлен, соответствующий сообщению \(r(x) = x^4 + x^3\).

Синдром \(s(x) = \mathrm{rem}(r(x), g(x)) = x\), s = 010

Произошла ошибка передачи. Синдром соответствует ошибке в предпоследнем бите.

Наиболее вероятное кодовое слово c = 011010, \(c(x) = x^4 + x^3 + x\).

Поскольку код построен систематически, первые (левые) \(k=n-r = 3\) бит являются исходным сообщением. \(m=011\)