Скляр Б. Цифровая связь (2003) (1151859), страница 83
Текст из файла (страница 83)
Код можно использовать для одновременного исправления и и обнаружения 33 ошибок, причем о < (3, а минимальное расстояние кода дается следующим выражением [4): г)„ш > а + )3 ь 1. (6.49) Прн появлении г или меньшего числа ошибок код способен обнаруживать и исправлять их. Если ошибок больше г, но меньше е+1, где е определяется уравнением (6.47), код может определять наличие ошибок, но исправить может только некоторые из них. Например, используя код с И„„, = 7, можно выполнить обнаружение и исправление со следующими значениями а и )3. Обнаружение (13) Исправление (а) 3 4 5 6 Заметим, что исправление ошибки подразумевает ее предварительное обнаружение. В приведенном выше примере (с тремя ошибками) все ошибки можно обнаружить и исправить. Если имеется пять ошибок, их можно обнаружить, но исправить можно только одну из них.
б.5.4. Визуализация пространства 6-кортежей на рис. 6.14 визуально представлено восемь кодовых слов, фи1урирующих в примере из раздела 6.4.3. Кодовые слова образованы посредством линейных комбинаций из трех независимых б-кортежей, приведенных в уравнении (6.26); сами кодовые слова образуют трехмерное подпространспю.
На рисунке показано, что такое подпросгранство полностью за1ито восемью кодовыми словами (большие черные круги); координаты подпространства умышленно выбраны неортогональными. На рис. 6.14 предпринята попытка изобразить все пространство, содержащее шестьдесят четыре б-кортежей, хотя точно нарисовать или составить такую модель невозможно. Каждое кодовое слово окружают сферические слои нли оболочки. Радиус внутренних непересекающихся слоев — это расстояние Хэмминга, равное 1; радиус внешнего слоя — это расстояние Хэмминга, равное 2. Большие расстоя- 372 Гнпп* П Кпнппннппкппнпоппннн.несть 1 ния в этом примере не рассматриваются. Для каждого кодового слова два показанных слоя заняты искаженными кодовыми словами.
На каждой внутренней сфере существует шесп таких точек (всего 48 точек), представляющих шесть возможных однобитовых ошибок в векторах, соответствующих каждому кодовому слову. Зги кодовые слова с однобиговыми возмущениями могут быль соотнесены только с одним кодовым словом; следовательно, такие ошибки могут быль исправлены.
Как видно из нормальной матрицы, приведенной на рис. 6.11, существует также одна двухбитовая модель ошибки, которая подаается исправлению. Всего существует ~ ~=15 разных двухбитовых моделей ошибки, которыми /61 (2! может быть искажено любое кодовое слово, но исправить можно только одну из них (в нашем примере это модель ошибки О 1 О О О 1).
Остальные четырнадцать двухбитовых моделей ошибки описываются векюрами, которые нельзя однозначно сопоставить с каким-либо одним кодовым словом; эти не поддающиеся исправлению модели ошибки дают векторы, которые эквивалентны искаженным векторам двух или большего числа кодовых слов. На рисунке все (56) исправимые кодовые слова с одно- и двухбиговыми искажениями показаны маленькими черными кругами. Искоженные кодовые слова, не поддающиеся исправлению, представлены маленькими прозрачными кругами. ью 1ОЬООЕ Рис.
б.14. Пример васьле кадовмк слов в пространстве б-кортежей При представлении свойств класса кодов, известных как совершенные коды (ратас! соде), рис. 6.14 весьма полезен. Код, исправляющий ошибки в г битах, называется совершенным, если нормальная матрица содержит все модели ошибки из г или меньшего числа ошибок и не содержит иных образуюших элементов классов смежности (отсутствует возможность исправления остаточных ошибок). В контексте рис. 6.14 совершенный код с коррекцией ошибок в г битах — это такой код, который (при использовании детектирования по принципу максимального правдоподобия) может исправить все искаженные кодовые слова, находящиеся на расстоянии Хэмминга г (или ближе) от исходного кодового слова, и не способен исправить ни одну из ошибок, находящихся на расстоянии, превышающем г.
Кроме того, рис. 6.14 способствует пониманию основной цели поиска хороших кодов. Предпочтительным является пространство, максимально заполненное кодовыми словами (эффективное использование введенной избыточности), а также желательно, чтобы кодовые слова были по возможности максимально удалены друг от друга.
Очевидно, что эти цели противоречивы. 5.5.5. Коррекция со стиранием ошибок Приемник можно сконструировать так, чтобы он объявлял символ стертым, если последний принят неоднозначно либо обнаружено наличие помех или кратковременных сбоев. Размер входного алфавита такого канала равен Д, а выходного — Д+ 1; лишний выходной символ называется меткой старания (егазцге йая), или просто стиранием (егазцге).
Если демодулятор допускает символьную ошибку, то для ее исправления необходимы два параметра, определяюшие ее распалалсение и правильнее значение символа. В случае двоичных символов эти требования упрощаются — нам необходимо только расположение ошибки. В то же время, если демодулятор объявляет символ стертми (при этом правильное значение символа неизвестно), расположение этого символа известно, поэтому декодирование стерто~о кодового слова может оказаться проша исправления ошибки. Код зашиты от ошибок можно использовать для исправления стертых символов или одновременного исправления ошибок и стертых символов.
Если минимальное расстояние кода равно И,, любая комбинация из р или меньшего числа стертых символов может быть исправлена при следуюшем условии [6[: Н, )р+1. (6.50) Предположим, что ошибки не появляются вне позиций стирания. Преимушество исправления посредством стираний качественно можно выразить так: если минимальное расстояние кода равно Н„, согласно уравнению (6.50), можно восстановить ̈́— 1 стирание.
Поскольку число ошибок, которые можно исправить без стирания информации, не превышает (И -1)/2, то преимушество исправления ошибок посредством стираний очевидно. Далее, любую комбинацию из а ошибок и у стираний можно исправить одновременно, если, как показано в работе [6[, (6.51) Ы„„, > 2а+ у+ 1. Одновременное исправление ошибок и стираний можно осушествить следующим образом.
Сначала позиции из у стираний замешаются нулями, и получаемое кодовое слово декодируется обычным образом. Затем позиции из у стираний замещаются единицами, и декодирование повторяется для этого варианта кодового слова. После об- работки обоих кодовых слов (одно с подставленными нулями, другое — с подставленными единицами) выбирается то из них, которое соответствует наименьшему числу ошибок, исправленных вне позиций стирания. Если удовлетворяется неравенство (6.51), то описанный метод всегда дает верное декодирование. Пример 6.6.
Коррекция со стиранием ошибок Рассмотрим набор кодовых слов, представленный в разделе 6.4.3. 000000 110100 0110!О 101110 !01001 011!01 110011 000111 Пусть передано кодовое слово 1!0011, в котором два крайних слева разряда приемник объявил стертыми. Проверьте, что лавре:кденную последовательность хх0011 можно исправить. Решение Поскольку И = р + 1 = 3, код может исправить р= 2 стирания. В этом легко убедиться иэ рис. 6.11 или приведенного выше перечня кодовых слов, сравнивая 4 крайних правых разряда хх0011 с каждым из допустимых кодовых слов. Дейсшителызо переданное кодовое слово — это ближайшее (с точки зрения рассгояния Хэмминга) к искаженной последовательности. 6.6.
Полезность нормальной матрицы 6.6.1. Оценка возможностей кода Нормальную матрицу можно представлять как организационный инструмент, картотеку, содержащую все возможные 2" записи в пространстве л-кортежей, в которой ничего не упущено и не продублировано. На первый взгляд может показаться, что выгода от использования этого инструмента ограничена малыми блочными кодами, поскольку для кодов длиной более л = 20 пространство л-кортежей насчитывает миллионы элементов. Впрочем, даже для больших кодов нормальная матрица позволяет определить важные исходные характеристики, такие как возможные компромиссы между обнаружением и исправлением ошибок и пределы возможносгей кода в коррекции ошибок.
Одно из таких ограничений, называемое пределом Хэммиига [7), описывается следующим образом: Количествобитчетности: л — х>!окз 1+~ )+( )+...+~ ) (6.52,а) или Количествоклассовсмсжности: 2" > 1+~ 71+~ ) 4...+~ ! . (6.52,6) Здесь величина ~ .), определяемая уравнением (6.16), представляет число способов Гл) Ы выбора из н бит)' ошибочных. Заметим, что сумма членов уравнения (6.52), находящихся в квадратных скобках, дает минимальное количество строк, которое должно присутствовать в нормальной матрице для исправления всех моделей ошибки„ вплоть до г-битовых ошибок.
Неравенство определяет нижнюю границу числа л — 1г бит четности (или 2" ' классов смежности) как функцию возможностей кола в коррекции г-битовых ошибок. Аналогичным образом можно сказать, что неравенство лает верхнюю границу возможностей кода в коррекции г-битовых ошибок как функцию числа л — 1 бит четности !или 2" ' классов смежности). Для обеспечения возможности коррекции г-битовых ошибок произвольных линейных блочных кодов (и, 1) необходимым условием является удовлетворение предела Хэмминга. Чтобы показать, как нормальная матрица может обеспечил визуальное представление этого предела, возьмем в качестве примера код БХЧ (127, 106). Матрица содержит все 2" = 2гл = 1,70х 10" л-кортежей пространства.
Верхняя строка матрицы содержит 2'= 2ки= 8,11х 10" кодовых слов; следовательно, зто число столбцов в матрице. Крайний левый столбец содержит 2" ' = 2" = 2 097 152 образующих элемента классов смежности; следовательно, это количество строк в матрице. Несмотря на то что число л-кортежей и кодовых слов просю огромно, нас не интересует конкретный вид каждого элемента матрицы. Основной интерес представляет количество классов смежности.
Существует 2 097 152 класса смежности и, следовательно, 2 097 151 модель ошибки, которую способен исправить этот код. Далее показано, каким образом это число классов смежности определяет верхний предел возможностей кода в коррекции г-битовых ошибок. Поскольку каждое кодовое слово содержит 127 бит, существует 127 возможностей допустить ошибку в одном бите. Рассчитываем количество возможностей появления двух ошибок — ~ 2 ! = 8 001. Затем переходим к трехбитовым ошибкам, поскольку ошибки, !127! Таблица 8.3.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
