Неравенством варшамова гильберта называют выражение
Обновлено: 22.12.2024
Пример. Пусть и , тогда , .
Далее операция при применении к двоичным словам будет означать поразрядное сложение без переноса, т.е. сложение по модулю 2 или "исключающее ИЛИ" ( XOR ).
Расстояние между двоичными словами и равно весу их поразрядной суммы, т.е. .
Если два слова различаются в каком-либо разряде, то это добавит единицу к весу их поразрядной суммы.
Следовательно, если и - слова длины , то вероятность того, что слово будет принято как , равна q^" />
.
Наример, вероятность того, что слово 1011 будет принято как 0011, равна .
Для возможности обнаружения ошибки в одной позиции минимальное расстояние между словами кода должно быть большим 1.
Иначе ошибка в одной позиции сможет превратить одно кодовое слово в другое, что не даст ее обнаружить.
Для того, чтобы код давал возможность обнаруживать все ошибки кратности, не большей , необходимо и достаточно, чтобы наименьшее расстояние между его словами было .
Достаточность доказывается конструктивно: если условие утверждения выполнено для , то в качестве декодирующей функции следует взять функцию, сообщающую об ошибке, если декодируемое слово отличается от любого из слов из образа . Необходимость доказывается от противного: если минимальное расстояние , то ошибка в позициях сможет превратить одно кодовое слово в другое.
C^i_np^q^i=C^_np^q^+\cdots+ C^_npq^+q^n\approx" />
при малых и не слишком маленьких _np^q^" />
.
Для того, чтобы код давал возможность исправлять все ошибки кратности, не большей , необходимо и достаточно, чтобы наименьшее расстояние между его словами было .
Пример. Рассмотрим -код, состоящий из , задающей отображение и , и , задающей отображение . Этот код (с тройным повторением) исправляет ошибки в одной позиции, т.к. минимальное расстояние между словами кода равно 3.
Если код исправляет все ошибки кратности и меньшей, то вероятность ошибочного приема слова длины очевидно не превосходит C^i_np^q^i" />
. Вероятность правильного приема в этом случае не меньше, чем
C^i_np^q^i=p^n+C^1_np^q+\cdots+C^k_np^q^k." />
Пример. Пусть передаваемое слово кодируется словом , а строка ошибок - . Тогда будет принято слово . Система, исправляющая ошибки, переведет его в 0110 и затем восстановит переданное слово 01.
Если система только обнаруживает ошибки и расстояние между любыми кодовыми словами , то любая строка ошибок с единственной единицей приведет к слову , которое не является кодовым.
Пример. Рассмотрим -код с проверкой четности. Множество кодовых слов - " />
. Ни одна из строк ошибок 001, 010, 100, 111 не переводит одно кодовое слово в другое. Поэтому однократная и тройная ошибки могут быть обнаружены.
Пример. Следующий -код обнаруживает две ошибки:
Этот же код способен исправлять однократную ошибку, потому что любые два кодовых слова отличаются по меньшей мере в трех позициях. Из того, что при , следует, что однократная ошибка приведет к приему слова, которое находится на расстоянии 1 от кодового слова, которое было передано. Поэтому схема декодирования, состоящая в том, что принятое слово переводится в ближайшее к нему кодовое, будет исправлять однократную ошибку. В двоичном симметричном канале вероятность правильной передачи одного блока будет не меньше чем .
Установлено 1 20 , что в -коде, минимальное расстояние между кодовыми словами которого , числа , (число дополнительных разрядов в кодовых словах) и должны соответствовать неравенству
+\cdots+C_n^1+1)," />
называемому неравенством или нижней границей Хэмминга . Кроме того, если числа , и соответствуют неравенству
^+C_^+\cdots+C_^1+1)," />
называемому неравенством или верхней границей Варшамова - Гильберта , то существует -код, исправляющий все ошибки веса и менее 2 20 .
Нижняя граница задает необходимое условие для помехозащитного кода с заданными характеристиками, т.е. любой такой код должен ему соответствовать, но не всегда можно построить код по подобранным, удовлетворяющим условию характеристикам. Верхняя граница задает достаточное условие для существования помехозащитного кода с заданными характеристиками, т.е. по любым подобранным, удовлетворяющим условию характеристикам можно построить им соответствующий код.
Упражнение 37 Имеется -код с проверкой четности. Вычислить вероятность того, что в случае ошибки этот код ее не обнаружит, если вероятность ошибки при передаче каждого бита равна 1%. Вычислить также вероятность ошибочной передачи без использования кода. Сделать аналогичные расчеты для случая, когда вероятность ошибки в десять раз меньше.
Упражнение 38 Вычислить минимальную и максимальную оценки количества дополнительных разрядов для кодовых слов длины , если требуется, чтобы минимальное расстояние между ними было . Рассмотреть случаи , и , .
Читайте также: