Помехоустойчивое кодирование и декодирование (1151930), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

При этом желательно, чтобычисло используемых проверочных символов было минимальным. К сожалению, задача определенияминимального числа проверочных символов, необходимых для обеспечения заданного кодового расстояния,не решена. Имеется лишь ряд оценок для максимального кодового расстояния при фиксированных п и k,которые часто используются при выяснении того, насколько построенный код близок к оптимальному.Можно показать [133], что если существует блочный линейный код (п, k), то для него справедливонеравенство⁄≥ log,(9.8)называемое верхней границей Хэмминга, где [(d – 1)/2] означает целую часть числа (d – 1)/2.Граница Хэмминга (9.8) близка к оптимальной для кодов с большими значениями k/n.

Для кодов смалыми значениями k/n более точной является верхняя граница Плоткина:r ≥ 2d – 2 – log2 (d).Можно также показать, что существует блочный линейный код (п, k) с кодовым расстоянием d, длякоторого справедливо неравенство≤ log,называемое нижней границей Варшамова—Гильберта.Таким образом, границы Хэмминга и Плоткина являются необходимыми условиями существованиякода, а граница Варшамова—Гильберта — достаточным.

Эти границы позволяют оценить эффективностьблочных кодов и целесообразность их применения.Линейные блочные кодыЛинейный (п, k)-код можно получить из k линейно независимых кодовых комбинаций путем ихпосимвольного суммирования по модулю 2 в различных сочетаниях. Исходные линейно независимые кодовыекомбинации называются базисными.Представим базисные кодовые комбинации в виде (k×n)-матрицы g11gG   21 ... g k1g12g 22...gk 2g1n ... g 2 n ....

... ... g kn ...(9.9)В теории кодирования матрица G называется порождающей. Тогда процесс кодирования заключается ввыполнении операцииB = AG,где А — вектор размерности k, соответствующий сообщению; В — вектор размерности п, соответствующийкодовой комбинации.Таким образом, порождающая матрица (9.9) содержит всю необходимую для кодирования информацию.Она должна храниться в памяти кодирующего устройства. Для двоичного кода объем памяти равен k×nдвоичных символов. При табличном задании кода кодирующее устройство должно запоминать п · 2kдвоичных символов.Две порождающие матрицы, отличающиеся друг от друга только порядком расположения столбцов,задают коды, которые имеют одинаковые расстояния Хэмминга между соответствующими кодовымикомбинациями, а, следовательно, и одинаковые корректирующие способности.

Такие коды называютсяэквивалентными.В качестве базисных комбинаций часто выбирают кодовые комбинации, содержащие по одной единицесреди информационных символов. При этом порождающую матрицу (9.9) удается записать в каноническойформе:100...00 g1k 1 010...00 g2 k 1G  I, P   ...... 000...01 g kk 1g1n ...

g 2 n ,... ... ... g kn ...(9.10)где I — единичная (k × k)-подматрица; P — (k × (п – k))-подматрица проверочных символов, определяющаясвойства кода. Матрица (9.10) задает систематический разделимый код. Можно показать, что для любоголинейного кода существует эквивалентный систематический код.Линейный (n, k)-код может быть задан так называемой проверочной матрицей Н размерности r × п. Приэтом некоторая комбинация В принадлежит коду только в том случае, если вектор В ортогонален всемстрокам матрицы Н, т.

е. если выполняется равенствоBHт = 0,(9.11)где T — символ транспонирования матрицы.Поскольку равенство (9.11) справедливо для любой кодовой комбинации, тоGHт = 0.Каноническая форма матрицы Н имеет вид g1k 1gH  P т , I   1k  2 ... g1ng 2 k 1 ... g kk 1 100...00 g 2 k  2 ... g kk  2 010...00 ,............

g 2 n ... g kn 000...01(9.12)где Рт — подматрица, столбцами которой служат строки подматрицы Р из соотношения (9.10); I — единичная(r × r)-подматрица.Подставляя (9.12) в (9.11), можно получать п – k уравнений видаkbk  j    gi k  j bi  0,j  1, 2, K , n  k ,(9.13)i 1которые называются уравнениями проверки.

Из (9.13) следует, что проверочные символы кодовыхкомбинаций линейного кода образуются различными линейными комбинациями информационных символов.Единицы в любой j-й строке подматрицы Рт, входящей в проверочную матрицу (9.12), указывают, какиеинформационные символы участвуют в формировании j-го проверочного символа.Очевидно, что линейный (n, k)-код можно построить, используя уравнения проверки (9.13). При этомпервые k символов кодовой комбинации информационные, а остальные п – k символов — проверочные,образуемые в соответствии с формулой (9.13).С помощью проверочной матрицы сравнительно легко можно построить код с заданным кодовымрасстоянием. Это построение основано на следующей теореме: кодовое расстояние линейного (n, k)-кодаравно d тогда и только тогда, когда любые d – 1 столбцов проверочной матрицы этого кода линейнонезависимы, но некоторые d столбцов проверочной матрицы линейно зависимы.Заметим, что строки проверочной матрицы линейно независимые.

Поэтому проверочную матрицу можноиспользовать в качестве порождающей для некоторого другого линейного (п, п – k)-кода, называемогодвойственным.Кодирующее устройство для линейного (п, k)-кода (рис. 9.22) состоит из k-разрядного сдвигающегорегистра и r = n – k блоков сумматоров по модулю 2. Информационные символы одновременно поступают навход регистра и на выход кодирующего устройства через коммутатор К. С поступлением k-гоинформационного символа на выходах блоков сумматоров в соответствии с уравнениями (9.13) формируютсяпроверочные символы, которые затем последовательно поступают на выход кодера.Процесс декодирования сводится к выполнению операции% т,S  BHгде S — вектор размерности n – k, называемый синдромом; B% — вектор принятой кодовой комбинации.Если принятая кодовая комбинация B% совпадает с одной из разрешенных В (это имеет место тогда,когда либо ошибки в принятых символах отсутствуют, либо при действии помех одна разрешенная кодоваякомбинация переходит в другую), то% т  0.S  BHВ противном случае S ≠ 0, причем вид синдрома зависит только от вектора ошибок е.

Действительно,% т  (B  e)H т  eH т ,S  BHгде В — вектор, соответствующий передаваемой кодовой комбинации. При S = 0 декодер принимает решениеоб отсутствии ошибок, а при S ≠ 0 — о наличии ошибок. Число различных синдромов, соответствующихразным сочетаниям ошибок, равно 2n–k – 1. По конкретному виду синдрома можно в пределахкорректирующей способности кода указать на ошибочные символы и исправить их.TkT2T1Б локс ум м ато р о впо m od 2Б локс ум м ато р о впо m od 2KВ ы хо дВ хо дБ локс ум м ато р о впо m od 2bk + 1bk + 2bnРис. 9.22. Структурная схема кодера линейного кодаДекодер линейного кода (рис. 9.23) состоит из k-разрядного сдвигающего регистра, n – k блоковсумматоров по модулю 2, схемы сравнения, анализатора ошибок и корректора.

Регистр служит длязапоминания информационных символов принятой кодовой последовательности, из которых в блокахсумматоров формируются проверочные символы. Анализатор ошибок по конкретному виду синдрома,получаемого в результате сравнения формируемых на приемной стороне и принятых проверочных символов,определяет места ошибочных символов. Исправление информационных символов проводится в корректоре.Заметим, что в общем случае при декодировании линейного кода с исправлением ошибок в памятидекодера должна хранитьсятаблица соответствий междусиндромамиивекторамиошибок, содержащая 2n–k строк.С приходом каждой кодовойкомбинации декодер долженперебрать всю таблицу.

Принебольших значениях п – k этаоперацияневызываетзатруднений.Однакодлявысокоэффективныхкодовдлиной п, равной несколькимдесяткам,разностьп–kпринимает такие значения, чтоперебор таблицы из 2n–k стрококазываетсяпрактическиневозможным. Например, длякода(63, 51),имеющегоРис.

9.23. Структурная схема декодера линейного кодакодовоерасстояниеd = 5,таблица состоит из 212 = 4096строк.При заданных значениях п и k существует 2k(n–k) линейных кодов. Задача заключается в выборенаилучшего (с позиции того или иного критерия) кода. Следует заметить, что до сих пор общие методысинтеза оптимальных линейных кодов не разработаны.Циклические кодыЦиклические коды относятся к классу линейных. Поэтому для их построения, в принципе, достаточнознать порождающую матрицу.Однако можно указать другой, более простой способ построения циклических кодов, основанный напредставлении кодовых комбинаций многочленами b(х) видаb(x) = bn–1 xn–1  bn–2 xn–2  …  b1 x  b0,где bi, i = 0, 1, …, n – 1, — символы кодовой комбинации.

Характеристики

Список файлов ответов (шпаргалок)