Неравенством варшамова гильберта называют выражение

Обновлено: 04.10.2024

Пример. Пусть и , тогда , .

Далее операция при применении к двоичным словам будет означать поразрядное сложение без переноса, т.е. сложение по модулю 2 или "исключающее ИЛИ" ( XOR ).

Расстояние между двоичными словами и равно весу их поразрядной суммы, т.е. .

Если два слова различаются в каком-либо разряде, то это добавит единицу к весу их поразрядной суммы.

Следовательно, если и - слова длины , то вероятность того, что слово будет принято как , равна q^" />
.

Наример, вероятность того, что слово 1011 будет принято как 0011, равна .

Для возможности обнаружения ошибки в одной позиции минимальное расстояние между словами кода должно быть большим 1.

Иначе ошибка в одной позиции сможет превратить одно кодовое слово в другое, что не даст ее обнаружить.

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

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

$\sum^n_<i=k+1></p> C^i_np^q^i=C^_np^q^+\cdots+ C^_npq^+q^n\approx$
при малых и не слишком маленьких _np^q^" />
.

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

Пример. Рассмотрим -код, состоящий из , задающей отображение и , и , задающей отображение . Этот код (с тройным повторением) исправляет ошибки в одной позиции, т.к. минимальное расстояние между словами кода равно 3.

Если код исправляет все ошибки кратности и меньшей, то вероятность ошибочного приема слова длины очевидно не превосходит C^i_np^q^i" />
. Вероятность правильного приема в этом случае не меньше, чем

$\sum^k_<i=0></p> C^i_np^q^i=p^n+C^1_np^q+\cdots+C^k_np^q^k.$

Пример. Пусть передаваемое слово кодируется словом , а строка ошибок - . Тогда будет принято слово . Система, исправляющая ошибки, переведет его в 0110 и затем восстановит переданное слово 01.

Если система только обнаруживает ошибки и расстояние между любыми кодовыми словами , то любая строка ошибок с единственной единицей приведет к слову , которое не является кодовым.

Пример. Рассмотрим -код с проверкой четности. Множество кодовых слов - " />
. Ни одна из строк ошибок 001, 010, 100, 111 не переводит одно кодовое слово в другое. Поэтому однократная и тройная ошибки могут быть обнаружены.

Пример. Следующий -код обнаруживает две ошибки:

$a_1=00\rightarrow00000=b_1,\qquad a_2=01\rightarrow01011=b_2,$

$a_3=10\rightarrow10101=b_3,\qquad a_4=11\rightarrow11110=b_4.$

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

Установлено 1 20 , что в -коде, минимальное расстояние между кодовыми словами которого , числа , (число дополнительных разрядов в кодовых словах) и должны соответствовать неравенству

$r \ge \log_2(C_n^k+C_n^<k-1></p> +\cdots+C_n^1+1),$
называемому неравенством или нижней границей Хэмминга . Кроме того, если числа , и соответствуют неравенству

$r > \log_2(C_</p> ^+C_^+\cdots+C_^1+1),$
называемому неравенством или верхней границей Варшамова - Гильберта , то существует -код, исправляющий все ошибки веса и менее 2 20 .

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

Упражнение 37 Имеется -код с проверкой четности. Вычислить вероятность того, что в случае ошибки этот код ее не обнаружит, если вероятность ошибки при передаче каждого бита равна 1%. Вычислить также вероятность ошибочной передачи без использования кода. Сделать аналогичные расчеты для случая, когда вероятность ошибки в десять раз меньше.

Упражнение 38 Вычислить минимальную и максимальную оценки количества дополнительных разрядов для кодовых слов длины , если требуется, чтобы минимальное расстояние между ними было . Рассмотреть случаи , и , .

Читайте также: