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

5.1. Какой вид будет иметь матрица двухкратных ошибок. Как она изменится по сравнению с матрицей однократных ошибок (5.11)?

5.2. Как связаны параметры двоичного представления синдромов (см. табл. 5.11) с общим числом вариантов возможных конфигураций обнаруживаемых и исправляемых ошибок при синдромном декодировании?

5.3. Как изменится формат синдромов, если применить метод синдромного декодирования для декодирования двухкратных ошибок?

5.4. Приведите обобщенную структурную схему синдромного декодера блочного кода (n, k). Какую функцию выполняет анализатор синдрома?

Задания

5.1. По принципам, изложенным в примере 5.1, изобразите структуру систематического блокового кода, предназначенного для обнаружения двухкратных ошибок с порождающей матрицей (4.6).

5.2. Задана порождающая матрица кода (7, 4):

.

Определите разрешенную кодовую комбинацию этого кода b, если задана комбинация первичного кода на входе кодера a = (1110).

5.3. определите кодовое расстояние кода (7, 4) с порождающей матрицей из задания 5.2.

5.4. Изобразите функциональную схему кодера кода (7, 4) с этой же порождающей матрицей.

6. Границы параметров блоковых кодов

6.1. Верхняя граница Хемминга [2, разд.3.2]

6.2. Нижняя граница Варшамова-Гилберта [2, разд.3.2]

6.3. Сложность реализации алгоритмов кодирования и декодирования.

6.1 Верхняя граница Хемминга

Одна из проблем теории кодирования состоит в поиске кодов, которые при заданной длине блока n и скорости кода R_код обеспечивают максимум кодового расстояния d_min. Пределы этих параметров определяются кодовыми границами, которые рассмотрены ниже.

Вывод верхней границы основан на соображениях сферической упаковки (граница сферической упаковки). При заданном минимальном расстоянии между разрешенными комбинациями кода d_min наибольшая скорость может быть достигнута, если сферы, окружающие каждую комбинацию, будут наиболее плотно упакованы. Объем каждой сферы равен , число сфер (число кодовых комбинаций кода) равно 2^k. Для лучшего кода суммарное количество сфер и число всех возможных комбинаций (2ⁿ) должны совпадать. Равенство достигается для плотноупакованных (совершенных) кодов. Область каждой кодовой комбинации представляет собой сферу радиуса (d_min – 1)/2, и эти области таких кодов, не пересекаясь, плотно заполняют собой все n-мерное пространство кодовых комбинаций. Отсюда следует неравенство:

.

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

. (6.1)

График верхней границы Хемминга для двоичных кодов показан на рис. 6.1 (кривая ВГХ). Граница Хемминга справедлива как для линейных, так и для нелинейных кодов.

6.2. Нижняя граница Варшамова-Гилберта

Для блоковых кодов можно получить нижнюю границу Варшамова-Гилберта, определяющую возможность существования кодов с параметрами R_код и d_min. Асимптотическая (для достаточно длинных кодов) форма этой границы имеет вид:

R_код  1 – H(d/n), (6.2)

где H(x) – двоичная энтропия. График нижней границы Варшамова-Гилберта для двоичных кодов показан на рис. 6.1. (кривая НГВГ). Граница гарантирует существование кодов, характеристики которых соответствуют точкам, расположенным по крайней мере на кривой (или выше ее). Анализ показывает, что большинство используемых на практике кодов конечной длины расположены выше границы Варшамова-Гилберта.

Поиск кодов, обеспечивающих заданное минимальное расстояние d_min и достаточно высокую скорость R_код при n, обеспечивающих в то же время возможность реализации алгоритмов декодирования приемлемой сложности, является одной из важных задач теории кодирования.