которые называются уравнениями проверки. Из (7.11) следует, что проверочные символы кодовых комбинаций линейного кода образуются различными линейными комбинациями информационных символов. Единицы в любой j-й строке подматрицы Р, входящей в проверочную матрицу (7.10), указывают, какие информационные символы участвуют в формировании j-го проверочного символа.
Очевидно, что линейный (п, k) код можно построить, используя уравнения проверки (7.11). При этом первые k символов кодовой комбинации информационные, а остальные п-k символов - проверочные, образуемые в соответствии с (7.11).
С помощью проверочной матрицы сравнительно легко можно построить код с заданным кодовым расстоянием. Это построение основано на следующей теореме: кодовое расстояние линейного (п, k) кода равно d тогда и только тогда, когда любые d-1 столбцов проверочной матрицы этого кода линейно независимы, но некоторые d столбцов проверочной матрицы линейно зависимы.
Заметим, что строки проверочной матрицы линейно независимые. Поэтому проверочную матрицу можно использовать в качестве порождающей для некоторого другого линейного кода (п, п-k), называемого двойственным.
Кодирующее устройство для линейного (п,k) кода (рис. на предыдущей стр.) состоит из k-разрядного сдвигающего регистра и r=п-k блоков сумматоров по модулю 2. Информационные символы одновременно поступают на вход регистра и на выход кодирующего устройства через коммутатор К. С поступлением k-го информационного символа на выходах блоков сумматоров в соответствии с уравнениями (7.11) формируются проверочные символы, которые затем последовательно поступают на выход кодера. Процесс декодирования сводится к выполнению операции
, где S — вектор размерностью (п-k), называемый синдромом, В- вектор принятой кодовой комбинации.
Если принятая комбинация В совпадает с одной из разрешенных В (это имеет место тогда, когда либо ошибки в принятых символах отсутствуют, либо из-за действия помех одна разрешенная кодовая комбинация переходит в другую), то
В противном случае S≠O, причем вид синдрома зависит только от вектора ошибок е. Действительно,
где В- вектор, соответствующий передаваемой кодовой комбинации. При S=0 декодер принимает решение об отсутствии ошибок, а при S≠O - о наличии ошибок. По конкретному виду синдрома можно в пределах корректирующей способности кода указать на ошибочные символы и их исправить.
Декодер линейного кода (рис. на следующей стр.) состоит из k- разрядного сдвигающего регистра, (п-k) блоков сумматоров по модулю 2, схемы сравнения, анализатора ошибок и корректора. Регистр служит для запоминания информационных символов принятой кодовой последовательности, из которых в блоках сумматоров формируются проверочные символы. Анализатор ошибок по конкретному виду синдрома, получаемого в результате сравнения формируемых на приемной стороне и принятых проверочных символов, определяет места ошибочных символов. Исправление информационных символов производится в корректоре. Заметим, что в общем случае при декодировании линейного кода с исправлением ошибок в памяти декодера должна храниться таблица соответствий между синдромами и векторами ошибок. С приходом каждой кодовой комбинации декодер должен перебрать всю таблицу. При небольших значениях (п-k) эта операция не вызывает затруднений. Однако для высокоэффективных кодов длиной п, равной нескольким десяткам, разность (п-k) принимает такие значения, что перебор таблицы оказывается практически невозможным. Например, для кода (63, 51), имеющего кодовое расстояние d=5, таблица состоит из 2^12 = 4096 строк.
Задача заключается в выборе наилучшего (с позиции того или иного критерия) кода. Следует заметить, что до сих пор общие методы синтеза оптимальных линейных кодов не разработаны.
Циклические коды.
Циклические коды относятся к классу линейных систематических. Поэтому для их построения в принципе достаточно знать порождающую матрицу.
Можно указать другой способ построения циклических кодов, основанный на представлении кодовых комбинаций многочленами b(х) вида:
где bn-1bn-2...bo - кодовая комбинация. Над данными многочленами можно производить все алгебраические действия с учетом того, что сложение здесь осуществляется по модулю 2.
Каждый циклический код (n, k) характеризуется так называемым порождающим многочленом. Им может быть любой многочлен р(х) степени n-k. Циклические коды характеризуются тем, что многочлены b(x) кодовых комбинаций делятся без остатка на р(х). Поэтому процесс кодирования сводится к отысканию многочлена b(x) по известным многочленам a(х) а р(х), делящегося на р(х), где a(х)- многочлен степени k-1, соответствующий информационной последовательности символов.
Очевидно, что в качестве многочлена b(x) можно использовать произведение a(х)р(х). Однако при этом информационные и проверочные символы оказываются перемешанными, что затрудняет процесс декодирования. Поэтому на практике в основном применяется следующий метод нахождения многочлена b(x).
Умножим многочлен а(х) на и полученное произведение разделим на р(х). Пусть (7.12)
где m(х)- частное, а с(х)- остаток. Так как операции суммирования и вычитания по модулю 2 совпадают, то выражение (7.12) перепишем в виде: (7.13)
Из (7.13) следует, что многочлен делится на р(х) и, следовательно, является искомым.
Многочлен имеет следующую структуру: первые n-k членов низшего порядка равны нулю, а коэффициенты остальных совпадают с соответствующими коэффициентами информационного многочлена а(х). Многочлен с(х) имеет степень меньше n-k. Таким образом, в найденном многочлене b(x) коэффициенты при х в степени n-k и выше совпадают с информационными символами, а коэффициенты при остальных членах, определяемых многочленом с(х), совпадают с проверочными символами. На основе приведенных схем умножения и деления многочленов и строятся кодирующие устройства для циклических кодов.
В качестве примера приведена схема кодера и декодера для кода (см. рис.) с порождающим многочленом:
Код имеет кодовое расстояние d=3, что позволяет ему исправлять все однократные ошибки.
Принятая кодовая комбинация одновременно поступает в буферный регистр сдвига, служащий для запоминания кодовой комбинации и для ее циклического сдвига, и на устройство деления на многочлен р(х) для вычисления синдрома. В исходном состоянии ключ находится в положении 1. После семи тактов буферный регистр оказывается загруженным, а в регистре устройства деления будет вычислен синдром. Если вес синдрома больше единицы, то декодер начинает производить циклические сдвиги комбинации в буферном регистре при отсутствии новой комбинации на входе и одновременно вычислять их синдромы s(x)ximodp(x) в устройстве деления. Если на некотором 1-м шаге вес синдрома окажется меньше 2, то ключ переходит в положение 2, обратные связи в регистре деления разрываются. При последующих тактах ошибки исправляются путем подачи содержимого регистра деления на вход сумматора по модулю 2, включенного в буферный регистр. После семи тактов работы декодера в автономном режиме исправленная комбинация в буферном регистре возвращается в исходное положение (информационные символы будут занимать старшие разряды).
Существуют и другие, более универсальные, алгоритмы декодирования.
К циклическим кодам относятся коды Хэмминга, которые являются примерами немногих известных совершенных кодов. Они имеют кодовое расстояние d=3 и исправляют все одиночные ошибки. Среди циклических кодов широкое применение нашли коды Боуза- Чоудхури- Хоквингема (БЧХ).
Сверточные коды
Методы описания сверточных кодов.
Кодер СК содержит регистр памяти для хранения определенного числа информационных символов и преобразователь информационной последовательности в кодовую последовательность. Процесс кодирования производится непрерывно. Скорость кода R=k/n, где k - число информационных символов, одновременно поступающих на вход кодера, n - число соответствующих им символов на выходе кодера. Схема простого кодера показана на рис. 1.1а.
Информационные двоичные символы u поступают на вход регистра с К разрядами. На выходах сумматоров по модулю 2 образуются кодовые символы a(1) и a(2). Входы сумматоров соединены с определенными разрядами регистра. За время одного информационного символа на выходе образуются два кодовых символа (R= 1/2). Возможно кодирование и с другими скоростями. При скорости 2/3 на вход кодера одновременно поступает k=2 информационных символа, на выходе при этом образуется n=3 кодовых символа. Схема такого кодера показана на рис. 1.1,6.
Рассматриваемый код называется сверточным, постольку последовательность кодовых символов а может быть определена как свертка информационных символов u с импульсным откликом кодера. На рис. 1.2 показано прохождение единичной последовательности u=100… через кодер.
Символы a(1) и a(2) на его выходе образуют импульсный отклик h= 00111011 00... Таким образом, если на входе кодера действует произвольная информационная последовательность и, то последовательность на его выходе есть сумма по модулю 2 всех импульсных откликов, обусловленных действием смещенных во времени символов 1. Сверточный кодер, как автомат с конечным числом состояний, может быть описан диаграммой состояний. Диаграмма представляет собой направленный граф и описывает все возможные переходы кодера из одного состояния в другое, а также содержит символы выходов кодера, которые сопровождают эти переходы.
Первоначально кодер находится в состоянии 00, и поступление на его вход информационного символа u=0 перевозят его также в состояние 00. При этом на выходе кодера будут символы a(1)a(2)=00. На диаграмме этот переход обозначается петлей 00, выходящей из состояния 00 и вновь возвращающейся в это состояние. Далее, при поступлении символа u=1 кодер переходит в состояние 10, при этом, на выходе будут символы a(1)a(2)=11. Этот переход из состояния 00 в состояние 10 обозначается пунктирной линией. Далее возможно поступление на вход кодера информационных символов 0 либо 1. При этом кодер переходит в состояние 01 либо 11, а символы на выходе будут 10 либо 01 соответственно. Процесс построения диаграммы заканчивается когда будут просмотрены все возможные переходы из одного состояния во все остальные.
Решетчатая диаграмма является разверткой диаграммы состояний во времени. На решетке состояния показаны узлами, а переходы соединяющими их линиями. После каждого перехода из одного состояния в другое происходит смещение на один шаг вправо. Решетчатая диаграмма дает наглядное представление всех разрешенных путей, по которым может продвигаться кодер при кодировании. Каждой информационной последовательности на входе кодера соответствует единственный путь по решетке. Построение решетки производится на основе диаграммы состояний. Исходное состояние S(1)S(2)=0. С поступлением очередного символа u=0 либо 1 возможны переходы в состояния 00 либо 10, обозначаемые ветвями 00 и 11. Процесс следует продолжить, причем через три шага очередной фрагмент, решетки будет повторяться. Пунктиром показан путь 11100001..., соответствующий поступлению на вход кодера информационной последовательности 1011...
Для описания кодера последовательности символов на его входе и выходе представляют с использованием оператора задержки:
Здесь индексы в скобках обозначают: i- номер входа кодера, 1≤ j≤ n, j- номер выхода кодера, 1≤i≤ k. Индексы без скобок (0, 1, 2, ...) обозначают дискретные моменты времени.
Процесс кодирования может быть представлен как умножение многочлена входной информационной последовательности u(D) на порождающие многочлены кода G(j)(D), которые описывают связи ячеек регистра кодера с его выходами (1.1):
Порождающий многочлен представим в виде ряда (1.2):
СК можно также задавать порождающей матрицей (1.3):
Порождающая матрица состоит из сдвигов базисной порождающей матрицы (верхняя строка матрицы О), которая, в свею очередь, состоит из элементарных матриц Gi, 0≤i≤k-1, содержащих k строк и n столбцов. Элементами этих матриц двоичных кодов являются символы 0 и 1.
Как при использовании блоковых кодов, процесс кодирования может быть представлен в матричной форме: A=UG (1.4)
,где U- полубесконечная матрица входных информационных символов, А- полубесконечная матрица символов на выходе кодера.
Декодирование сверточных кодов.
Алгебраические методы декодирования основаны на использовании алгебраических свойств кодовых последовательностей. В ряде случаев эти методы приводят к простым реализациям кодека. Такие алгоритмы являются неоптимальными, так как используемые алгебраические процедуры декодирования предназначены для исправления конкретных (и не всех) конфигураций ошибок в канале. Алгебраические методы отождествляют с поэлементным приемом последовательностей, который для кодов с избыточностью, как известно, дает худшие результаты, чем прием в целом.
Вероятностные методы декодирования значительно ближе к оптимальному приему в целом, так как в этом случае декодер оперирует с величинами, пропорциональными вероятностям, оценивает и сравнивает вероятности различных гипотез и на этой основе выносит решения о передаваемых символах.
Пороговое декодирование.
Вероятностные методы декодирования достаточно сложны в реализации, хотя и обеспечивают высокую помехоустойчивость. Наряду с ними широко применяют более простые алгоритмы. Для этой цели используют класс СК, допускающих пороговое декодирование.
Рассмотрим систематический код со скоростью 1/2 и многочленами:
Схема кодека на рисунке. Моделью двоичного канала являются сумматоры по
модулю 2, на входы которых, кроме кодовых последовательностей а(1) и а(2), поступают ошибки е(1) и е(2). Декодер содержит аналог кодера, в котором принятым символам формируется копия проверочной последовательности. В формирователе синдрома (сумматоре по модулю 2) образуется последовательность синдромов, которая поступает на вход синдромного регистра. Наборам ошибок соответствуют определенные конфигурации синдромов последовательности S. Если количество ненулевых синдромов превышает определенный порог, на выходе порогового элемента появляется символ коррекции, который в корректоре используется для исправления ошибки в информационном символе.
Список использованной литературы:
1. Радиотехнические системы передачи информации, под ред. В. В. Калмыкова
2. Сверточные коды в системах передачи информации, учебное пособие
Страницы: 1, 2
