Основы теории принятая статистических решений 1051 31 страница

й = г + ё = (и + е)+ё = и + (е + ё) (6.40)

Если правильно вычислили ошибку: ё = е, тогда оценка U совпадает с переданным ко­довым словом U. С другой стороны, если оценка ошибки неверна, декодер неверно оп­ределит переданное кодовое слово и мы получим необнаружимую ошибку декодирования.

Пример 6.4. Исправление ошибок

Пусть передано кодовое слово U = 101110 из примера в разделе 6.4.3 и принят вектор г = 001110. Нужно показать, как декодер, используя таблицу соответствия синдромов (табл 6 2), может исправить ошибку.

Решение

Рассчитывается синдром г.

S= [001 1 10] Н^г=[10 0]

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

ё= 1 0 0 0 0 0

Исправленный вектор равен следующему:

U = г+ё=

=00111 0+1 00000=.

= 10 1110 '

Поскольку оцененная модель ошибки в этом поимере совпадает с действительной моделью ошибки, процедура исправления ошибки дает U = U.

Можно видеть, что процесс декодирования искаженного кодового слова путем предвари­тельного обнаружения и последующего исправления ошибки можно сравнить с аналогичной

б 4 Линрйныр блочный копы

медицинской процедурой. Пациент (потенциально искаженный вектор) приходит в меди­цинское учреждение (декодер). Врач проводит серию тестов (умножение на Н^г), чтобы оп­ределить симптомы болезни (синдром). Допустим, врач нашел характерные пятна на рентге­нограмме пациента. Опытный врач может непосредственно установить связь между симпто­мом и болезнью (моделью ошибки). Начинающий врач может обратиться к медицинскому справочнику (табл. 6.2) для определения соответствия между симптомом (синдромом) и бо­лезнью (моделью ошибки). Последний шаг заключается в назначении соответствующего ле­чения, которое устранит болезнь (уравнение (6 40)). Продолжая аналогию двоичных кодов и медицины, можно сказать, что уравнение (6.40) — это несколько необычный способ лече­ния. Пациент излечивается в результате повторного заболевания той же болезнью.

6.4.9. Реализация декодера

Если код короткий, например рассмотренный ранее код (6, 3), декодер может быть реализован в виде довольно простой схемы. Рассмотрим шаги, которые должны быть предприняты декодером: (1) вычислить синдром, (2) локализовать модель ошибки и (3) осуществить сложение по модулю 2 модели ошибки и принятого вектора (что при­водит к устранению ошибки). В примере 6.4, имея искаженный вектор, мы покажем, как с помощью последовательности этих шагов можно получить исправленное кодо­вое слово. Сейчас мы рассмотрим схему, показанную на рис. 6.12, где реализованы логические элементы исключающего ИЛИ и И, которые позволяют получить тот же результат для любой модели с одним ошибочным битом в коде (6, 3). Из табл. 6.2 и уравнения (6.39) можно записать все разряды синдрома через разряды принятых кодо­вых слов:

S = гН^г,

и

■*1 ^{= г}\ + ^ГА + ^г6<

S2 = Г₂+ Г4 + Г₅, s S₂ = r₃ + r₅ + Г5.

Мы используем эти выражения для синдромов при связывании схемы на рис. 6.12. Логический элемент “исключающее ИЛИ” — это и есть реализация той самой опера­ции сложения (или вычитания) по модулю 2, поэтому он обозначен тем же символом Маленький кружок в конце каждой линии, входящей в элемент И, означает опе­рацию логического дополнения сигнала.

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

Заметим, что с методической точки зрения рис. 6.12 составлен так, чтобы выделить алгебраические этапы декодирования — вычисление синдрома и модели ошибки, а также выдачу исправленных выходных данных. В реальной ситуации код (/г, к) обычно выбирается систематическим.

Гпаой A /ouonuLiAQ ^гчтлгчгчиашла' ияГ'ТК 1

Декодеру не нужно выдавать полное кодовое слово; на выходе у него должны быть только биты данных. Поэтому схема на рис. 6.12 упрощается за счет удаления заштри­хованных элементов. Для более длинных кодов такая реализация намного сложнее; более предпочтительной методикой декодирования является последовательная схема, а не рассмотренный здесь параллельный метод [4]. Важно также подчеркнуть, что схема на рис. 6.12 позволяет определять и исправлять только модели кода (6,3) с од­ним ошибочным битом. Исправление моделей с двумя ошибочными битами потребу­ет дополнительной схемы.

6.4.9.1. Векторные обозначения

Выше кодовые слова, модели ошибок, принятые векторы и синдромы обознача­лись как векторы U, е, г и S. Для упрощения записи индексы, сопутствующие кон­кретному вектору, в основном, опускались. Хотя, если быть точным, каждый из век­торов U, е, г и S должен записываться в следующем виде;

Xj= {х_ьх₂,... }

Рассмотрим диапазон индексов j и i в контексте кода (6, 3), приведенного в табл. 6.1. Для кодового слова U, индекс j = 1,..., 2* показывает, что имеется 2³ = 8 отдельных ко­довых слов, а индекс i= 1,..., п демонстрирует, что каждое кодовое слово составлено из «= 6 бит. Для исправимой модели ошибки е, индекс j = 1,..., 2"'¹ означает, что имеется 2³ = 8 образующих элементов классов смежности (7 ненулевых исправимых моделей ошибки), а индекс i = 1,..., п указывает, что каждая модель ошибки составле­на из п = 6 бит. Для принятого вектора г₇ индекс j= 1,..., 2" показывает, что имеется 2^б = 64 /1-кортежей, прием которых возможен, а индекс /'= 1,..., п указывает, что каж­дый принятый л-кортеж состоит из п = 6 бит. И наконец, для синдрома S, индекс j =

1,..., п- к означает, что каждый синдром состоит из п - к = 3 бит. В этой главе индек­сы часто опускаются, и векторы U,, е_я г, и S, зачастую обозначаются как U, е, г и S. Читателю следует помнить, что для этих векторов индексы всегда подразумеваются, даже в тех случаях, когда они опущены для простоты записи.

ft Л Пмиоммио fSnnuwuio k-nm-j I >’»

6.5. Возможность обнаружения и исправления ошибок

6.5.1. Весовой коэффициент двоичных векторов и расстояние между ними

Конечно же, понятно, что правильно декодировать можно не все модели ошибки. Воз­можности кода для исправления ошибок в первую очередь определяются его структурой. Весовой коэффициент Хэмминга (Hamming weight) w(U) кодового слова U определяется как число ненулевых элементов в U. Для двоичного вектора это эквивалентно числу единиц в векторе. Например, если U=100101 101, то w(U) = 5. Расстояние Хэмминга (Hamming distance) между двумя кодовыми словами U и V, обозначаемое как d(U, V), определяется как количество элементов, в которых они отличаются.

U= 1 00101101 V=011110 100 d(U, V) = 6

Согласно свойствам сложения по модулю 2, можно отметить, что сумма двух двоич­ных векторов является другим двоичным вектором, двоичные единицы которого рас­положены на тех позициях, которыми эти векторы отличаются.

U +V=1 1 1 0 1 1001

Таким образом, можно видеть, что расстояние Хэмминга между двумя векторами рав­но весовому коэффициенту Хэмминга их суммы, т.е. d(U, V) = w(U + V). Также видно, что весовой коэффициент Хэмминга кодового слова равен его расстоянию Хэмминга до нулевого вектора.

6.5.2. Минимальное расстояние для линейного кода

Рассмотрим множество расстояний между всеми парами кодовых слов в пространстве V„. Наименьший элемент этого множества называется минимальным расстоянием кода и обозначается d_aш. Как вы думаете, почему нас интересует именно минимальное рас­стояние, а не максимальное? Минимальное расстояние подобно наиболее слабому звену в цепи, оно дает нам меру минимальных возможностей кода и, следовательно, характеризует его мощность.

Как обсуждалось ранее, сумма двух произвольных кодовых слов дает другой эле­мент кодовых слов подпространства. Это свойство линейных кодов формулируется просто: если U и V — кодовые слова, то и W = U + V тоже должно быть кодовым сло­вом. Следовательно, расстояние между двумя кодовыми словами равно весовому ко­эффициенту третьего кодового слова, т.е. d(U, V) = w(U + V) = w(W). Таким образом, минимальное расстояние линейного кода можно определить, не прибегая к изучению расстояний между всеми комбинациями пар кодовых слов. Нам нужно лишь опреде­лить вес каждого кодового слова (за исключением нулевого вектора) в подпространст­ве; минимальный вес соответствует минимальному расстоянию d_mm. Иными словами, d_tмп соответствует наименьшему из множества расстояний между нулевым кодовым словом и всеми остальными кодовыми словами.

6.5.3. Обнаружение и исправление ошибок

Задача декодера после приема вектора г заключается в оценке переданного кодового слова U,. Оптимальная стратегия декодирования может быть выражена в терминах алгоритма максимального правдоподобия (см. приложение Б); считается, что передано было слово U„ если

Я(гIU.) = шах Р(г|U,). (6.41)

по всем U_;

Поскольку для двоичного симметричного канала (binary symmetric channel — BSC) правдоподобие U, относительно г обратно пропорционально расстоянию между г и Ц, можно сказать, что передано было слово U,, если

rf(r|U,)= min d(r|U.). (6.42)

по всем U j

Другими словами, декодер определяет расстояние между г и всеми возможными пере­данными кодовыми словами U,, после чего выбирает наиболее правдоподобное U,, для которого

d(r,U_t) <d(r,Uj) для i,j = 1,..., М и i*j, (6.43)

где М = 2* — это размер множества кодовых слов. Если минимум не один, выбор меж­ду минимальными расстояниями является произвольным. Наше обсуждение метрики расстояний будет продолжено в главе 7.

На рис. 6.13 расстояние между двумя кодовыми словами U и V показано как рас­стояние Хэмминга. Каждая черная точка обозначает искаженное кодовое слово. На рис. 6.13, а проиллюстрирован прием вектора г_ь находящегося на расстоянии 1 от кодового слова U и на расстоянии 4 от кодового слова V. Декодер с коррекцией ошибок, следуя стратегии максимального правдоподобия, выберет при принятом векторе Г] кодовое слово U. Если г, получился в результате появления одного оши­бочного бита в переданном векторе кода U, декодер успешно исправит ошибку. Но если же это произошло в результате 4-битовой ошибки в векторе кода V, деко­дирование будет ошибочным. Точно так же, как показано на рис. 6.13, б, двойная ошибка при передаче U может привести к тому, что в качестве принятого вектора будет ошибочно определен вектор г₂, находящийся на расстоянии 2 от вектора U и на расстоянии 3 от вектора кода V. На рис. 6.13, в показана ситуация, когда в каче­стве принятого вектора ошибочно определен вектор г₃, который является результа­том тройной ошибки при передаче и находится на расстоянии 3 от вектора кода U и на расстоянии 2 от вектора V. Из рис. 6.13 видно, что если задача состоит только в обнаружении ошибок, а не в их исправлении, то можно определить искаженный вектор — изображенный черной точкой и представляющий одно-, двух-, трех- и че­тырехбитовую ошибку. В то же время пять ошибок при передаче могут привести к приему кодового слова V, когда в действительности было передано кодовое слово U; такую ошибку невозможно будет обнаружить.

Из рис. 6.13 можно видеть, что способность кода к обнаружению и исправлению ошибок связана с минимальным расстоянием между кодовыми словами. Линия реше­ния на рисунке служит той же цели, что и в процессе демодуляции, — для разграни­чения областей решения.

б 5 Втмпжнппть пйнягл/жрния м ипппавления ошибок

Линия

решений

Область 1	Область 2
U г,	V
U гг	V

б)

Гз

В)

Рис. 6.13 Возможности определения и исправления ошибок: а) принятый век­тор г_ь- б) принятый вектор г₂; в) при­нятый вектор г₃

В примере, приведенном на рис. 6.13, критерий принятия решения может быть следую­щим: выбрать U, если г попадает в область 1, и выбрать V, если г попадает в область 2. Выше показывалось, что такой код (при d_nm = 5) может исправить две ошибки. Вообще, способность кода к исправлению ошибок t определяется, как максимальное число гарантиро­ванно исправимых ошибок на кодовое слово, и записывается следующим образом [4]:

(6.44)

Здесь bd означает наибольшее целое, не превышающее х. Часто код, который исправ­ляет все искаженные символы, содержащие ошибку в t или меньшем числе бит, также может исправлять символы, содержащие t +1 ошибочных бит. Это можно увидеть на рис. 6.11. В этом случае d_mm = 3, поэтому из уравнения (6.44) можно видеть, что испра­вимы все модели ошибки из t = 1 бит. Также исправима одиночная модель ошибки, со­держащая /+1 (т.е. 2) ошибочных бит. Вообще, линейный код (и,к), способный ис­правлять все символы, содержащие t ошибочных бит, может исправить всего 2^п~^к мо­делей ошибок. Если блочный код с возможностью исправления символов, имеющих ошибки в t бит, применяется для исправления ошибок в двоичном симметричном ка­нале с вероятностью перехода р, то вероятность ошибки сообщения Рм (вероятность того, что декодер совершит неправильное декодирование и и-битовый блок содержит ошибку) можно оценить сверху, используя уравнение (6.18):

(6.45)

Гпяпя R Кяняпкнпр тгиппиянир’ чягп, 1

Оценка переходит в равенство, если декодер исправляет все модели ошибок, содер­жащие до г ошибочных бит включительно, но не модели с числом ошибочных бит, большим г. Такие декодеры называются декодерами с ограниченным расстоянием. Веро­ятность ошибки в декодированном бите Р_в зависит от конкретного кода и декодера. Приближенно ее можно выразить следующим образом [5]:

(6.46)

В блочном коде, прежде чем исправлять ошибки, необходимо их обнаружить. (Или же код может использоваться только для определения наличия ошибок.) Из рис. 6.13 видно, что любой полученный вектор, который изображается черной точкой (искаженное кодовое слово), можно определить как ошибку. Следовательно, возмож­ность определения наличия ошибки дается следующим выражением:

(6.47)

Блочный код с минимальным расстоянием d„_m гарантирует обнаружение всех моделй ошибок, содержащих d_am - 1 или меньшее число ошибочных бит. Такой код также спо­собен обнаружить и более длинную часть модели ошибки, содержащую d_am или более ошибок. Фактически код (я, к) может обнаружить 2" - 2^к моделей ошибок длины и. Объ­ясняется это следующим образом. Всего в пространстве 2" л-кортежей существует 2" - 1 возможных ненулевых моделей ошибок. Даже правильное кодовое слово — это потенци­альная модель ошибки. Поэтому всего существует 2^к - 1 моделей ошибки, которые иден­тичны 2* — 1 ненулевым кодовым словам. При появлении любая из этих 2⁴ — 1 моделей ошибки изменяет передаваемое кодовое слово U, на другое кодовое слово U,. Таким об­разом, принимается кодовое слово U,, и его синдром равен нулю. Декодер принимает U, за переданное кодовое слово, и поэтому декодирование дает неверный результат. Следо­вательно, существует 2^к -1 необнаружимых моделей ошибки. Если модель ошибки не совпадает с одним из 2^к кодовых слов, проверка вектора г с помощью синдромов дает ненулевой синдром и ошибка успешно обнаруживается. Отсюда следует, что существует ровно 2" - 2* выявляемых моделей ошибки. При больших и, когда 2^к«2", необнаружи- мой будет только незначительная часть моделей ошибки.

6.5.3.1. Распределение весовых коэффициентов кодовых слов

Пусть Aj — количество кодовых слов с весовым коэффициентом j в линейном коде (л, к). Числа А₀, Л,,..., А_п называются распределением весовых коэффициентов этого кода. Если код применяется только для обнаружения ошибок в двоичном симметричном канале, то вероятность того, что декодер не сможет определить ошибку, можно рас­считать, исходя из распределения весовых коэффициентов кода [5]:

(6.48)

где р — вероятность перехода в двоичном симметричном канале. Если минимальное расстояние кода равно d_nml, значения от А, до А_н равны нулю.

mn ¹

fi Ч Rn'iMH^unr'Tk п^иап\лк-оима \л мгппяппоииа гм ыЛ

Пример 6.5. Вероятность необнаруженной ошибки в коде

Пусть код (6, 3), введенный в разделе 6.4.3, используется только для обнаружения наличия ошибок. Рассчитайте вероятность необнаруженной ошибки, если применяется двоичный симметричный канал, а вероятность перехода равна 10^_г.

Решение

Распределение весовых коэффициентов этого кода выглядит следующим образом: А₀=1, А\ — Аг = 0, Ai = 4, А₅ = О, А₆ = 0. Следовательно, используя уравнение (6.48), можно запи­сать следующее:

Р*& = 4рЧ 1 - Р? + Ър\ 1 -р)².

Для р = 10“² вероятность необнаруженной ошибки будет равна 3,9 х 10^-6.

6.5.3.2. Одновременное обнаружение и исправление ошибок

Возможность исправления ошибок следует из гарантированного максимума (г), где t определяется уравнением (6.44), для одновременного обнаружения класса ошибок. Код можно использовать для одновременного исправления а и обнаружения (3 ошибок, причем а<(3, а минимальное расстояние кода дается следующим выражением [4]:

d„m S а + Р + 1. (6.49)

При появлении г или меньшего числа ошибок код способен обнаруживать и исправ­лять их. Если ошибок больше г, но меньше е+1, где е определяется уравнени­ем (6.47), код может определять наличие ошибок, но исправить может только некото­рые из них. Например, используя код с d„= 7, можно выполнить обнаружение и ис­правление со следующими значениями аир.

Обнаружение (Р) Исправление (а)

3 3

4 2

5 1

6 О

Заметим, что исправление ошибки подразумевает ее предварительное обнаружение. В приведенном выше примере (с тремя ошибками) все ошибки можно обнаружить и исправить. Если имеется пять ошибок, их можно обнаружить, но исправить можно только одну из них.

6.5.4. Визуализация пространства 6-кортежей

На рис. 6.14 визуально представлено восемь кодовых слов, фигурирующих в примере из раздела 6.4.3. Кодовые слова образованы посредством линейных комбинаций из трех неза­висимых 6-кортежей, приведенных в уравнении (6.26); сами кодовые слова образуют трех­мерное подпространство. На рисунке показано, что такое подпространство полностью за­нято восемью кодовыми словами (большие черные круги); координаты подпространства умышленно выбраны неортогональными. На рис. 6.14 предпринята попытка изобразить все пространство, содержащее шестьдесят четыре 6-кортежей, хотя точно нарисовать или составить такую модель невозможно. Каждое кодовое слово окружают сферические слои или оболочки. Радиус внутренних непересекающихся слоев — это расстояние Хэмминга, равное 1; радиус внешнего слоя — это расстояние Хэмминга, равное 2. Большие расстоя-

Гланя fi Кянялкнпр кплиппрянирг чяптк 1

ния в этом примере не рассматриваются. Для каждого кодового слова два показанных слоя заняты искаженными кодовыми словами. На каждой внутренней сфере существует шесть таких точек (всего 48 точек), представляющих шесть возможных однобитовых ошибок в векторах, соответствующих каждому кодовому слову. Эти кодовые слова с однобитовыми возмущениями могут быть соотнесены только с одним кодовым словом; следовательно, такие ошибки могут быть исправлены. Как видно из нормальной матрицы, приведенной на рис. 6.11, существует также одна двухбитовая модель ошибки, которая поддается ис­правлению. Всего существует ^ j = 15 разных двухбитовых моделей ошибки, которыми

может быть искажено любое кодовое слово, но исправить можно только одну из них (в нашем примере это модель ошибки 0 1 0 0 0 1). Остальные четырнадцать двухбитовых моделей ошибки описываются векторами, которые нельзя однозначно сопоставить с ка­ким-либо одним кодовым словом; эти не поддающиеся исправлению модели ошибки дают векторы, которые эквивалентны искаженным векторам двух или большего числа кодовых слов. На рисунке все (56) исправимые кодовые слова с одно- и двухбитовыми искажения­ми показаны маленькими черными кругами. Искаженные кодовые слова, не поддающиеся исправлению, представлены маленькими прозрачными кругами.

При представлении свойств класса кодов, известных как совершенные коды (perfect code), рис. 6.14 весьма полезен. Код, исправляющий ошибки в г битах, называется со­вершенным, если нормальная матрица содержит все модели ошибки из г или мень­шего числа ошибок и не содержит иных образующих элементов классов смежности (отсутствует возможность исправления остаточных ошибок). В контексте рис. 6.14 со­вершенный код с коррекцией ошибок в г битах — это такой код, который (при ис­пользовании детектирования по принципу максимального правдоподобия) может ис­править все искаженные кодовые слова, находящиеся на расстоянии Хэмминга г (или ближе) от исходного кодового слова, и не способен исправить ни одну из ошибок, на­ходящихся на расстоянии, превышающем г.

Кроме того, рис. 6.14 способствует пониманию основной цели поиска хороших ко­дов. Предпочтительным является пространство, максимально заполненное кодовыми словами (эффективное использование введенной избыточности), а также желательно, чтобы кодовые слова были по возможности максимально удалены друг от друга. Оче­видно, что эти цели противоречивы.

6.5.5. Коррекция со стиранием ошибок

Приемник можно сконструировать так, чтобы он объявлял символ стертым, если по­следний принят неоднозначно либо обнаружено наличие помех или кратковременных сбоев. Размер входного алфавита такого канала равен Q, а выходного — Q + 1; лишний выходной символ называется меткой стирания (erasure flag), или просто стиранием (erasure). Если демодулятор допускает символьную ошибку, то для ее исправления необ­ходимы два параметра, определяющие ее расположение и правильное значение символа. В случае двоичных символов эти требования упрощаются — нам необходимо только расположение ошибки. В то же время, если демодулятор объявляет символ стертым (при этом правильное значение символа неизвестно), расположение этого символа из­вестно, поэтому декодирование стертого кодового слова может оказаться проще исправ­ления ошибки. Код защиты от ошибок можно использовать для исправления стертых символов или одновременного исправления ошибок и стертых символов. Если мини­мальное расстояние кода равно d,_mu любая комбинация из р или меньшего числа стер­тых символов может быть исправлена при следующем условии [6]:

d_ltm>p+l. (6.50)

Предположим, что ошибки не появляются вне позиций стирания. Преимущество ис­правления посредством стираний качественно можно выразить так: если минимальное расстояние кода равно d_mm, согласно уравнению (6.50), можно восстановить d,_n„ - 1 стирание. Поскольку число ошибок, которые можно исправить без стирания инфор­мации, не превышает (d_mm - 1)/2, то преимущество исправления ошибок посредством стираний очевидно. Далее, любую комбинацию из а ошибок и у стираний можно ис­править одновременно, если, как показано в работе [6],

с1_пш> 2а +у + 1. (6.51)

Одновременное исправление ошибок и стираний можно осуществить следующим образом. Сначала позиции из у стираний замещаются нулями, и получаемое кодовое слово декодируется обычным образом. Затем позиции из у стираний замещаются еди­ницами, и декодирование повторяется для этого варианта кодового слова. После об­
работки обоих кодовых слов (одно с подставленными нулями, другое — с подставлен­ными единицами) выбирается то из них, которое соответствует наименьшему числу ошибок, исправленных вне позиций стирания. Если удовлетворяется неравенст­во (6.51), то описанный метод всегда дает верное декодирование.

Пример 6.6. Коррекция со стиранием ошибок

Рассмотрим набор кодовых слов, представленный в разделе 6.4.3.

0 110100 011010 101110 101001 011101 110011 000111

Пусть передано кодовое слово 110011, в котором два крайних слева разряда приемник объ­явил стертыми. Проверьте, что поврежденную последовательность хх0011 можно исправить. Решение

Поскольку d_mn = р + 1 = 3, код может исправить р = 2 стирания. В этом легко убедиться из рис. 6.11 или приведенного выше перечня кодовых слов, сравнивая 4 крайних правых разряда xxOOll с каждым из допустимых кодовых слов. Действительно переданное кодовое слово — это ближайшее (с точки зрения расстояния Хэмминга) к искаженной последовательности.

6.6. Полезность нормальной матрицы

6.6.1. Оценка возможностей кода

Нормальную матрицу можно представлять как организационный инструмент, картотеку, содержащую все возможные 2" записи в пространстве и-кортежей, в которой ничего не упущено и не продублировано. На первый взгляд может показаться, что выгода от исполь­зования этого инструмента ограничена малыми блочными кодами, поскольку для кодов длиной более л = 20 пространство н-кортежей насчитывает миллионы элементов. Впрочем, даже для больших кодов нормальная матрица позволяет определить важные исходные ха­рактеристики, такие как возможные компромиссы между обнаружением и исправлением ошибок и пределы возможностей кода в коррекции ошибок. Одно из таких ограничений, называемое пределом Хэмминга [7], описывается следующим образом:

Количество бит четности: п-к> log₂

или

Здесь величина ^, определяемая уравнением (6.16), представляет число способов

выбора из п бит j ошибочных. Заметим, что сумма членов уравнения (6.52), нахо­дящихся в квадратных скобках, дает минимальное количество строк, которое долж­но присутствовать в нормальной матрице для исправления всех моделей ошибки, вплоть до f-битовых ошибок. Неравенство определяет нижнюю границу числа п-к бит четности (или Т~^к классов смежности) как функцию возможностей кода в кор­рекции r-битовых ошибок. Аналогичным образом можно сказать, что неравенство дает верхнюю границу возможностей кода в коррекции f-битовых ошибок как

функцию числа п-к бит четности (или 2ⁿ~^k классов смежности). Для обеспечения возможности коррекции r-битовых ошибок произвольных линейных блочных кодов (п, к) необходимым условием является удовлетворение предела Хэмминга.

Чтобы показать, как нормальная матрица может обеспечить визуальное представление этого предела, возьмем в качестве примера код БХЧ (127,106). Матрица содержит все 2^п~ 2¹²⁷ = 1/70Х10³⁸ /1-кортежей пространства. Верхняя строка матрицы содержит 2*= 2¹⁰⁶ = 8,11 х 10³¹ кодовых слов; следовательно, это число столбцов в матрице. Крайний левый столбец содержит 2"~^к = 2²' =2 097 152 образующих элемента классов смежности; следова­тельно, это количество строк в матрице. Несмотря на то что число л-кортежей и кодовых слов просто огромно, нас не интересует конкретный вид каждого элемента матрицы. Ос­новной интерес представляет количество классов смежности. Существует 2 097 152 класса смежности и, следовательно, 2 097 151 модель ошибки, которую способен исправить этот код. Далее показано, каким образом это число классов смежности определяет верхний предел возможностей кода в коррекции r-битовых ошибок.

Поскольку каждое кодовое слово содержит 127 бит, существует 127 возможностей до­пустить ошибку в одном бите. Рассчитываем количество возможностей появления двух (127^

ошибок— I 2 J = 8 001. Затем переходим к трехбитовым ошибкам, поскольку ошибки,

упомянутые выше, — это Лишь незначительная часть всех 2 097 151 моделей ошибки.

(127^

Итак, существует К I = 333 375 возможностей совершить трехбитовую ошибку. Эти рас­четы приведены в табл. 6.3; там же показано, что нулевая модель ошибки требует наличия первого класса смежности. Затем перечислены требования одно-, двух- и трехбитовых ошибок. Также показывается количество классов смежности, необходимое для коррекции каждого типа ошибок, и общее количество классов смежности, необходимых для коррек­ции ошибок всех типов, вплоть до требуемого типа ошибки. Из этой таблицы можно ви­деть, что код (127,106) способен исправить все модели, содержащие 1, 2 или 3 ошибочных бита, причем это составляет только 341 504 из 2 097 152 возможных классов смежности. Неиспользованные 1 755 648 строк говорят о больших потенциальных возможностях в кор­рекции ошибок, чем было использовано. Действительно, в матрицу можно попытаться втиснуть все возможные 4-битовые ошибки. Но при взгляде на табл. 6.3 становится со­вершенно ясно, что это невозможно, поскольку, как показывает последняя строка табли­цы, число оставшихся в матрице классов смежности значительно меньше общего числа классов смежности, требуемого для коррекции 4-битовых ошибок. Следовательно, предел Хэмминга описанного кода (127, 106) гарантирует исправление всех ошибок вплоть до 3-битовых.

Дата добавления: 2015-10-28