Скляр Б. Цифровая связь (2003) (1151859), страница 84
Текст из файла (страница 84)
Предел возможностей коррекции длн кода (127, 106) Количество битовых ошибок Количество необходимых Общее число необходимых классов смежности классов смежности 1 127 800! 333375 10334625 ! 128 8!29 34!504 10676!29 упомянул ае выше, — это лишь незначительная часп всех 2 097 151 моделей ошибки. Итак, существует ~ 3 ~ = 333 375 возможностей совершить трехбитовую ошибку.
Зги рас- 61273 четы приведены в табл. 6.3; там же показано, что нулевая модель ошибки требует наличия первого класса смежности. Затем перечислены требования одно-, двух- и трехбитовых ошибок. Также показывается количество классов смежности, необходимое для коррекции каждого типа ошибок, и общее количество классов смежности, необходимых для коррекции ошибок всех типов, вплоть до требуемого типа ошибки. Из этой таблицы можно видеть, что код (127, 106) способен исправить все модели, содержащие 1, 2 или 3 ошибочных бита, причем это составляет только 341504 из 2097152 возможных классов смежности. Неиспользованные 1 755 648 строк говорят о больших потенциальных возможностях в коррекции ошибок, чем было использовано, Действительно, в матрицу можно попытаться втиснуть все возможные 4-битовые ошибки.
Но при взгляде на табл. 6.3 становится совершенно ясно, что это невозможно, поскольку, как показывает последняя строка таблицы, число оставшихся в матрице классов смежности значительно меньше общего числа классов смежности, требуемого для коррекции 4-битовых ошибок. Следовательно, предел Хэмминга описанного кода (127, 106) гарантирует исправление всех ошибок вплоть до З-битовых. 6.6.2. Пример кода (п, й) Нормальная матрица дает возможность взглянуть на возможные компромиссы между исправлением и обнаружением ошибок. Рассмотрим пример кода (л,х) и факторы, определяющие выбор конкретных значений (л, х).
1. Для получения нетривиального соотношения между исправлением и обнаружением ошибок желательно, чтобы код имел возможности коррекции ошибок, по крайней мере, с г= 2. Согласно уравнению (6.44), минимальное расстояние при этом равнои', =2г+1=5. 2. Чтобы кодовая система была нетривиальной, желательно, чтобы количество бит данных было не менее А = 2. Следовательно, число кодовых слов 2'= 4, Далее будем считать наш код следующим: (л, 2).
3. Нас интересует минимальное значение л, которое позволит исправлять все одно- и двухбнтовые ошибки. В этом примере каждый из 2" л-кортежей в матрице будет табулирован. Минимальное значение и нас интересует потому, что при каждом увеличении л на единицу число л-кортежей в нормальной матрице удваивается. Это условие, разумеется, диктуется только соображениями удобства использования таблицы.
Для реальных прикладных кодов минимальное значение я выбирается по разным причинам — эффективносп использования полосы пропускания и простота системы. Если при выборе л используется предел Хэмминга, то л следует выбрать равным 7. В то же время размерность полученного кода (7, 2) не соответствует указанным выше требованиям г= 2 и И„, = 5. Чтобы увидеть это, следует ввести другую верхнюю границу возможностей кода в коррекции г-битовых ошибок (или и'„).
Эта граница, называемая лредея Плолжила [7), определяется следующим образом: лх2" йпип— 2 — 1 (б.54) 6.6.3. Разработка кода (8, 2) Ответ на вопрос, как выбираются кодовые слова из лросврансглва 2г я-кортезкей, неод- нозначен, хотя определенные возможности выбора все же существуют. Ниже перечис- лены некоторые моменты, которые могут указать наилучшее решение.
6.6. Полезность нормальной матрицы 377 В общем случае, линейный код (л, )г) должен удовлетворять всем перечисленным выше условиям, включая возможности коррекции ошибок (или минимальное расстоянис. Для высокоскоростных кодов из удовлетворения предела Хэмминга следует удовлетворение предела Плоткина; это справедливо, например, для рассмотренного ранее кода (127, 10б).
Для кодов с низкими скоростями передачи существует обходной путь удовлетворения названных требований (7). Поскольку в нашем примере речь идет именно о таких кодах, важно оценить их возможности в коррекции ошибок с помощью предела Плоткина. Поскольку и'„= 5, из уравнения (6.53) получаем, что л должно быть равно 8; следовательно, для удовлетворения всех требований, поставленных в этом примере, минимальная размерность кода равна (8„2). Можно ли практически использовать подобный код (8, 2)? Этого делать не стоит, поскольку это потребует слишком большой полосы пропускания; лучше выбрать более эффективный код.
Данный код мы используем здесь только с методической целью, единственным его преимуществом являются удобные размеры его нормальной матрицы. 1. Количество кодовых слов2'=2'=4. 2. Среди кодовых слов должен быть нулевой вектор. 3. Следует учесть свойство замкнутости — сумма двух любых кодовых слов в пространстве должна давать кодовое слово из этого же пространства. 4. Каждое кодовое слово содержит 8 двоичных разрядов. 5.
Поскольку 4,=5, весовой коэффициент каждого кодового слова (за исключением нулевого) также должен быть не менее 5 (в силу свойства замкнутости). Весовой коэффициент вектора определяется как число ненулевых компонентов этого вектора. б. Предположим, что код является систематическим; значит, 2 крайних правых бита каждого кодового слова являются соответствующими битами сообщения.
Далее предлагается вариант набора кодовых ным выше требованиям. Сообщения 00 О! !О !1 слов, удовлетворяющих всем перечислен- Кодовые слова 00000000 11110001 00111110 11001!11 Создание набора кодовых слов может выполняться совершенно произвольно; нужно только неуклонно следовать свойствам весовых коэффициентов и придерживаться систематической формы кода. Выбор первых нескольких кодовых слов обычно очень прост. Далее процесс, как правило, усложняется и возможность выбора все больше ограничивается за счет свойства замкнутости.
6.6.4. Соотношение между обнаружением и исправлением ошибок Для кодовой системы (8, 2), выбранной в предыдущем разделе, матрицу генератора (Ахи) =(2 х 8) можно записать в следующем виде; 0 0 1 1 1 1 1 0~ 1 1 1 1 0 0 0 1~ 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 1 1 1 1 ! 1 1 0 0 Н г 37в Глава б Декодирование начинается с расчета синдрома, что можно представлять как изучение "симптомов" ошибки. Для кода (л,/с) (л — х)-битовый синдром Я является произведением принятого л-битового вектора г и транспонированной проверочной матрицы Н размерностью (л — х) хи. Проверочная матрица Н построена таким образом, что строки матрицы С ортогональны строкам матрицы Н, т.е. СН = О.
В нашем примере кода (8, 2) Я вЂ” это 6-битовый вектор, а Н вЂ” матрица размером 6 х 8, где Синдром для каждой модели ошибки можно рассчитать, исходя из уравнения (6.37), а именно Я гНт 1=1 2" ' где Я, — один из 2" "=64 синдромов, а е, — один из 64 образующих элементов классов смежности (моделей ошибки) в нормальной матрице. На рис.
6.15, помимо самой нормальной матрицы, показаны все 64 синдрома для кода (8,2). Набор синдромов рассчитывался с помощью уравнения (6.37); позиции произвольной строки (смежный класс) нормальной матрицы имеют один и тот же синдром. Исправление искаженного кодового слова осуществляется путем расчета его синдрома и локализации моделей ошибки, соответствующей этому синдрому. В заключение модель ошибки прибавляется (по модулю 2) к поврежденному кодовому слову, что и даст правильное кодовое слово.
Из уравнения (6.49), повторно приведенного ниже, видно, что между возможностями обнаружения и исправления ошибок существует некий компромисс, ограничиваемый расстоянием. Н„>а+В+1 Здесь а представляет количество исправляемых битовых ошибок, а  — количество обнаруживаемых битовых ошибок, причем В > а. В коде (8, 2) возможны следующие компромиссы между этими двумя величинами: Обнаружение (р) Исправление (а) Из данной таблицы видно, что код (8, 2) можно использовать только для исправления ошибок; это означает, что код вначале обнаруживает В=2 ошибки, после чего они исправляются.
Если пожертвовать возможностью исправления и использовать код лля исправления только однобитовых ошибок, то возможность обнаружения ошибки возрастает до 1) = 3 ошибок. И наконец, если целиком отказаться от исправления ошибок, то декодер сможет обнаруживать ошибки с В = 4. В случае, если ошибки только обнаруживаются, реализация декодера будет очень простой: производится вычисление синдрома и обнаруживается ошибка при появлении любого ненулевого синдрома.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
