Групповые коды, исправляющие кратные ошибки

Для того, чтобы групповой код исправлял не только одиночные, но и кратные ошибки, каждой конкретной как одиночной, так и кратной ошибке должен однозначно соответствовать свой синдром. Метод сопоставления синдромов одиночным ошибкам изложен ранее. Рассмотрим образование синдромов кратных ошибок на простейшем примере построения синдромов двойных ошибок.

Пример. Пусть синдром ошибки в 1-м разряде декодируемой комбинации имеет вид 0001, а в 4-м разряде - 1001. Это означает, что символ а₁ входит в 1-е и 4-е равенства, а символ а₄ - только в 1-е равенство. Если произойдут ошибки одновременно в 1-м и 4-м разрядах, то равенство, в которое входят символы а₁ и а₄ останется выполненным, так как

(символ - противоположен символу а_i, т.е. если а_i=1, то =0 и наоборот). В соответствии со структурой синдромов ни а₁, ни а₄ во 2-е и
4-е равенства не входят, и следовательно, на их выполнение не влияют. Поэтому при ошибках в 1-м и 4-м разрядах не будет выполняться только
4-е равенство, а значит, синдром такой парной ошибки имеет вид 1000, что соответствует сумме по модулю 2 синдромов в 1-м и 4-м разрядах: 1001Å 0001=1000.

Итак, синдром двойной ошибки равен сумме (по модулю 2) синдромов соответствующих одиночных. Студенту рекомендуется самостоятельно убедиться, что для ошибок любой кратности справедлив тот же вывод. Для однозначности опознавания ошибок при суммировании синдромов одиночных ошибок должны формироваться не повторяющиеся синдромы, т.е. не используемые для опознавания других ошибок.

Для пояснения вернемся к рассмотренному ранее коду (7, 4). Предположим, что произошли ошибки в 1-м и 4-м разрядах. Синдром такой двойной ошибки 001 + 011 = 010. Но он уже используется: соответствует ошибке во 2-м разряде, т.е. данный код не исправляет двойных ошибок. Из этого, в частности, следует еще и такой вывод: синдромы одиночных ошибок в информационных разрядах кодов, исправляющих двойные ошибки, должны содержать не менее четырех единиц. В самом деле, допустим, что синдром ошибки в одном из информационных разрядов имеет вид 00000111, синдром ошибки в 1-м разряде (проверочном) - 00000001, во 2-м - 00000010, в 3-м - 00000100. Тогда синдром ошибок в 1-м и 2-м разрядах совпал бы с синдромом ошибок в этом информационном и 3-м разрядах (00000011), что привело бы к невозможности однозначного декодирования. Кроме того, в синдромах ошибок в информационных разрядах единицы должны быть расположены так, чтобы сумма двух синдромов ошибок в информационных разрядах имела не менее трех единиц и не повторялась в виде одинаковых комбинаций.

Литература:

[1] стр. 235-246. [2] стр. 257-282. [3] стр. 131-148.

Контрольные вопросы:

1. В большинстве случаев источники информации вырабатывают сообщения, содержащие избыточную информацию. Почему этот избыток не используется в системах связи непосредственно для обнаружения и исправления ошибок?

2. Что называется основанием дискретного кода?

3. Какие коды называются систематическими, а какие - несистематическими?

4. Дайте определение конечной группы.

5. Почему некоторые виды корректирующих кодов называют групповыми?

6. В чем заключается свойство замкнутости подгруппы разрешенных комбинаций группового кода?

7. Что называется дистанцией Хэмминга в бинарных блочных кодах?

8. Каким должно быть минимальное расстояние Хэмминга в бинарных блочных кодах?

9. Каким должно быть минимальное расстояние Хэмминга в коде, исправляющем ошибки кратности К?

10. Каким должно быть минимальное расстояние Хэмминга в коде, обнаруживающем ошибки кратности К?

11. Как строится порождающая матрица группового кода?

12. Какое минимальное количество единиц должны иметь разрешенные комбинации кода, исправляющего одиночные ошибки?

13. Какое количество единиц должны иметь разрешенные комбинации группового кода, исправляющего двойные ошибки?

14. Какое количество единиц должны иметь разрешенные комбинации группового кода, обнаруживающего двойные ошибки?

15. Что называется синдромом ошибки в групповых кодах?

16. Объясните принцип составления проверочной матрицы группового кода.

17. Поясните принцип составления системы проверочных равенств по заданной проверочной матрице группового кода.

18. Источник информации вырабатывает сообщение в виде последовательности букв алфавита с основанием L=15. Для передачи информации по каналу связи используется бинарный код. Какая требуется разрядность блочного корректирующего кода?

19. Основание кода источника информации L=32. Определите необходимую разрядность безызбыточных комбинаций после перехода на бинарный код.

20. Задана разрядность безызбыточной комбинации и кратность исправляемых кодом ошибок. Определите необходимое количество разрядов, отводимых под проверочные символы.

21. Что называется вектором ошибки?

22. Как соотносятся между собой векторы одиночных и кратных ошибок в групповых кодах?

23. Сколько единиц должен содержать синдром ошибки в проверочном разряде группового кода?

Задачи:

1. Записать проверочную матрицу группового кода 7, 4, отводя под проверочные символы разряды: а) 1, 2 и 4-й; б) 1, 2 и 3-й, в) 5, 6 и 7-й. Закодировать безызбыточную комбинацию 0001.

2. Записать проверочную матрицу группового кода, 15, 11, отводя под проверочные символы разряды: а) 1, 2, 4 и 8-й; б) 1, 2, 3 и 4-й;
в) 12, 13, 14 и 15-й. Составить порождающую матрицу.

3. Составить проверочную матрицу группового кода 8, 2, отводя под информационные символы разряды: а) 7-й и 8-й; б) 1-й и 2-й; в) 1-й и 5-й. Закодировать безызбыточную комбинацию 11.

4. Для группового кода 7, 4 (задача 1, a) составить систему проверочных равенств для декодирования мажоритарным методом.

5. Для группового кода 7, 4 (задача 1, б) составить систему проверочных равенств для декодирования по синдромам.

6. Для группового кода 8, 2 (задача 3, а) составить систему проверочных равенств для декодирования мажоритарным методом.