Реферат: Избыточные коды

КафедраРадиотехнических Системреферат по избыточным кодам

Преподаватель: Смердова Н. Е.

Группа: РТ 9505

Студент: Матвеев А. Н.

Дата сдачи:Май 1999 года.

Москва, 1999 г.

Вступление.

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

Для предотвращения потерь информации вканале были придуманы избыточные коды (коды с избыточностью). Преимуществоизбыточного кода в том, что при приеме его с искажением (количество искаженныхсимволов зависит от степени избыточности и структуры кода) информация можетбыть восстановлена на приемнике.

Существуют избыточные коды с обнаружением (они только обнаруживаютошибку) и коды с исправлением (эти коды обнаруживают место ошибки и исправляютее).

Для различных помех в канале существуют различные по своей структуре иизбыточности коды. Обычно избыточность кодов находится в пределах 10…60% иличуть больше. Избыточность 1/4 (25%)применяется при записи информации на лазерные диски и в системах цифровогоспутникового ТВ.

Классификация кодов.

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

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

Блочные коды бывают разделимыми и неразделимыми. К разделимым относятсякоды, в которых символы по их назначению могут быть разделены на информационныесимволы, несущие информацию о сообщениях и проверочные. Такие коды обозначаютсякак (n, k), гдеn — длина кода, k — число информационных символов. Число комбинацийв коде не превышает 2^k. Кнеразделимым относятся коды, символы которых нельзя разделить по их назначениюна информационные и проверочные.

Коды с постоянным весом характеризуются тем, что их кодовые комбинациисодержат одинаковое число единиц: Примером такого кода является код “3 из 7”, вкотором каждая кодовая комбинация содержит три единицы и четыре нуля(стандартных телеграфный код № 3).

<img src="/cache/referats/3986/image004.gif" v:shapes="_x0000_s1026">
Кодыс постоянным весом позволяют обнаружить все ошибки кратности q=1,...,nзаисключением случаев, когда число единиц, перешедших в нули, равно числу нулей,перешедших в единицы. В полностью асимметричных каналах, в которых имеетместо только один вид ошибок (преобразование нулей в единицы или единиц внули), такой код дозволяет обнаружить все ошибки. В симметричных каналахвероятность необнаруженной ошибки можно определить как вероятностьодновременного искажения одной единицы и одного нуля:

где Pошвероятность искажениясимвола.

Среди разделимых кодов различают линейные и нелинейные. К линейнымотносятся коды, в которых поразрядная сумма по модулю 2 любых двух кодовых словтакже является кодовым словом. Линейный код называется систематическим, еслипервые kсимволов его любой кодовой комбинации являютсяинформационными, остальные (n — k)символов — проверочными.

<img src="/cache/referats/3986/image006.gif" v:shapes="_x0000_s1027">
Средилинейных систематических кодов наиболее простой код (n,n-k), содержащий один проверочный символ, которыйравен сумме по модулю 2 всех информационных символов. Этот код, называемыйкодом с проверкой на четность, позволяет обнаружить все сочетания ошибокнечетной кратности. Вероятность необнаруженной ошибки в первом приближенииможно определить как вероятность искажения двух символов:

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

Примером нелинейного кода является код Бергера, укоторого проверочные символы представляют двоичную запись числа единиц впоследовательности информационных символов. Например, таким является код:00000; 00101; 01001; O111O; 10001; 10110; 11010; 11111. Коды Бергераприменяются в асимметричных каналах. В симметричных каналах они обнаруживаютвсе одиночные ошибки и некоторую часть многократных.

Непрерывные коды характеризуются тем, чтооперации кодирования и декодирования производятся над непрерывной последовательностьюсимволов без разбиения ее на блоки. Среди непрерывных наиболее применимысверточные коды.

Как известно различают каналы с независимыми игруппирующимися ошибками. Соответственно помехоустойчивые коды можно разбить надва класса: исправляющие независимые ошибки и исправляющие пакеты ошибок. Далеебудут рассматриваться в основном коды, исправляющие независимые ошибки. Этообъясняется тем, что хотя для исправления пакетов ошибок разработано многоэффективных кодов, на практике целесообразнее использовать коды, исправляющиенезависимые ошибки вместе с устройством перемежения символов или декорреляцииошибок. При этом символы кодовой комбинации не передаются друг за другом,перемешиваются с символами других кодовых комбинаций. Если интервал междусимволами, принадлежащими одной кодовой комбинации, сделать больше чем “память”канала, то ошибки в пределах кодовой комбинации можно считать независимыми, чтои позволяет использовать коды, исправляющие независимые ошибки.

Блочные коды. Построение кодеков.

Линейные коды.

Из определения следует, что любой линейный код (п, k)можнополучить из k линейно независимыхкодовых комбинаций путем их посимвольного суммирования по модулю 2 в различныхсочетаниях. Исходные линейно независимые кодовые комбинации называютсябазисными.

Представим базисные кодовые комбинации в виде матрицы размерностью nXk

(7.7)

Втеории кодирования она называется порождающей. Тогда процесс кодированиязаключается в выполнении операции: B=AG,

где А- вектор размерностью k, соответствующий сообщению, В- векторразмерностью п, соответствующийкодовой комбинации.

<img src="/cache/referats/3986/image010.gif" v:shapes="_x0000_s1029">
Такимобразом, порождающая матрица (7.7) содержит всю необходимую для кодированияинформацию. Она должна храниться в памяти кодирующего устройства. Длядвоичного кода объем памяти равен kXnдвоичных символов. Притабличном задании кода кодирующее устройство должно запоминать <img src="/cache/referats/3986/image012.gif" v:shapes="_x0000_s1030">

двоичныхсимволов.

Две порождающие матрицы, которые отличаются друг отдруга только порядком расположения столбцов, задают коды, которые имеютодинаковые расстояния Хэмминга между соответствующими кодовыми комбинациями, аследовательно, одинаковые корректирующие способности. Такие коды называютсяэквивалентными.

<img src="/cache/referats/3986/image014.gif" v:shapes="_x0000_s1031">
В качестве базисных комбинаций часто выбирают кодовые комбинации, содержащие поодной единице среди информационных символов. При этом порождающую матрицуудается записать в канонической форме (7.8)

где I — единичная kXkподматрица, P-kX(n-k)- подматрицапроверочных символов, определяющая свойства кода. Матрица задаетсистематический код. Можно показать, что для любого линейного кода существуетэквивалентный систематический код.

<img src="/cache/referats/3986/image016.gif" v:shapes="_x0000_s1032">
Линейный(п, k) код может быть задан проверочнойматрицей Н размерности (rХп). При этом комбинация В принадлежит коду только в том случае,если вектор В ортогонален всем строкам матрицы Н, т. е. если выполняетсяравенство (7.9)

<img src="/cache/referats/3986/image018.gif" v:shapes="_x0000_s1035">
гдет—символ транспонирования матрицы. Так как это равенство справедливо для любойкодовой комбинации, то

<img src="/cache/referats/3986/image020.gif" v:shapes="_x0000_s1036">
Каноническаяформа матрицы Н имеет вид (7.10)

где P — подматрица, столбцами которой служат строки подматрицы Р (7.8), I-единичнаяrXrподматрица. Подставляя (7.10) в (7.9), можно получать п—k уравнений вида (7.11)

<img src="/cache/referats/3986/image022.gif" v:shapes="_x0000_s1037">
которыеназываются уравнениями проверки. Из (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) формируются проверочные символы, которыезатем последовательно поступают на выход кодера. Процесс декодирования сводитсяк выполнению операции

<img src="/cache/referats/3986/image026.gif" v:shapes="_x0000_s1038">
,где S— вектор размерностью (п-k), называемый синдромом, В-вектор принятой кодовой комбинации.

<img src="/cache/referats/3986/image028.gif" v:shapes="_x0000_s1039">
Еслипринятая комбинация В совпадает содной из разрешенных В (это имеет место тогда, когда либо ошибки в принятыхсимволах отсутствуют, либо из-за действия помех одна разрешенная кодоваякомбинация переходит в другую), то

<img src="/cache/referats/3986/image030.gif" v:shapes="_x0000_s1042">
Впротивном случае S≠O, причем вид синдрома зависит только от вектораошибок е. Действительно,

где В-вектор, соответствующий передаваемой кодовой комбинации. При S=0 декодер принимает решение об отсутствии ошибок,а при S≠O — о наличии ошибок. По конкретному виду синдромаможно в пределах корректирующей способности кода указать на ошибочные символыи их исправить.

Декодер линейного кода (рис. на следующей стр.) состоит из k — разрядного сдвигающего регистра, (п-k)блоков сумматоров по модулю 2, схемы сравнения, анализатора ошибок икорректора. Регистр служит для запоминания информационных символов принятойкодовой последовательности, из которых в блоках сумматоров формируютсяпроверочные символы. Анализатор ошибок по конкретному виду синдрома,получаемого в результате сравнения формируемых на приемной стороне и принятыхпроверочных символов, определяет места ошибочных символов. Исправлениеинформационных символов производится в корректоре. Заметим, что в общем случаепри декодировании линейного кода с исправлением ошибок в памяти декодера должнахраниться таблица соответствий между синдромами и векторами ошибок. С приходомкаждой кодовой комбинации декодер должен перебрать всю таблицу. При небольшихзначениях (п-k) эта операция невызывает затруднений. Однако для высокоэффективных кодов длиной п, равной нескольким десяткам, разность (п-k) принимает такие значения, чтоперебор таблицы оказывается практически невозможным. Например, для кода (63,51), имеющего кодовое расстояние d=5,таблица состоит из 2^12 = 4096 строк.

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

Циклические коды.

Циклические коды относятся к классу линейных систематических. Поэтомудля их построения в принципе достаточно знать порождающую матрицу.

Можно указать другой способ построения циклических кодов, основанный напредставлении кодовых комбинаций многочленами b(х)вида:

<img src="/cache/referats/3986/image034.gif" v:shapes="_x0000_s1054">
гдеbn-1bn-2...bo — кодовая комбинация. Над данными многочленамиможно производить все алгебраические действия с учетом того, что сложениездесь осуществляется по модулю 2.

Каждый циклический код (n, k)характеризуется так называемым порождающим многочленом. Им может быть любоймногочлен р(х)степени n-k.Циклические коды характеризуются тем, что многочлены b(x)кодовых комбинаций делятсябез остатка на р(х).Поэтому процесс кодирования сводится к отысканию многочлена b(x)поизвестным многочленам a(х)а р(х),делящегося на р(х), где a(х)- многочлен степени k-1, соответствующий информационнойпоследовательности символов.

<img src="/cache/referats/3986/image036.gif" v:shapes="_x0000_s1055">
Очевидно,что в качестве многочлена b(x)можноиспользовать произведение a(х)р(х).Однако при этом информационные и проверочные символы оказываются перемешанными,что затрудняет процесс декодирования. Поэтому на практике в основномприменяется следующий метод нахождения многочлена b(x).

<img src="/cache/referats/3986/image038.gif" v:shapes="_x0000_s1056">
Умножиммногочлен а(х) на и полученное произведение разделим на р(х).Пусть (7.12)

где m(х) — частное, а с(х) — остаток. Так как операции суммирования и вычитания по модулю 2 совпадают, товыражение (7.12) перепишем в виде: (7.13)

<img src="/cache/referats/3986/image043.gif" v:shapes="_x0000_s1059"> <img src="/cache/referats/3986/image044.gif" v:shapes="_x0000_s1058">
Из(7.13) следует, что многочлен делитсяна р(х)и,следовательно, является искомым.

Многочлен имеетследующую структуру: первые n-kчленов низшего порядка равны нулю, а коэффициенты остальных совпадают ссоответствующими коэффициентами информационного многочлена а(х). Многочленс(х)имеетстепень меньше n-k.Таким образом, в найденном многочлене b(x)коэффициенты при х в степени n-kи выше совпадают синформационными символами, а коэффициенты при остальных членах, определяемыхмногочленом с(х),совпадают с проверочными символами. На основе приведенных схем умножения иделения многочленов и строятся кодирующие устройства для циклических кодов.

В качестве примера приведена схема кодера и декодера для кода (см. рис.) с порождающим многочленом:

<img src="/cache/referats/3986/image048.gif" v:shapes="_x0000_s1062">
Кодимеет кодовое расстояние 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...

<img src="/cache/referats/3986/image054.gif" v:shapes="_x0000_s1045">
Дляописания кодера последовательности символов на его входе и выходе представляютс использованием оператора задержки:

Здесьиндексы в скобках обозначают: i — номер входа кодера, 1≤ j≤ n, j — номер выхода кодера, 1≤i≤ k.Индексы без скобок (0, 1, 2, ...) обозначают дискретные моменты времени.

<img src="/cache/referats/3986/image056.gif" v:shapes="_x0000_s1046">
Процесскодирования может быть представлен как умножение многочлена входнойинформационной последовательности u(D)на порождающие многочленыкода G(j)(D),которые описывают связи ячеек регистра кодера с его выходами (1.1):

<img src="/cache/referats/3986/image058.gif" v:shapes="_x0000_s1047">
Порождающий многочлен представим в виде ряда (1.2):

СКможно также задавать порождающей матрицей (1.3):

<img src="/cache/referats/3986/image060.gif" v:shapes="_x0000_s1048">
Порождающая матрица состоит из сдвиговбазисной порождающей матрицы (верхняя строка матрицы О), которая, в свею очередь,состоит из элементарных матриц Gi, 0≤i≤k-1, содержащих kстроки nстолбцов. Элементами этих матриц двоичных кодовявляются символы 0 и 1.

Какпри использовании блоковых кодов, процесс кодирования может быть представлен в матричной форме: A=UG (1.4)

, где U — полубесконечная матрицавходных информационных символов, А-полубесконечная матрица символов на выходе кодера.

Декодирование сверточных кодов.

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

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

Пороговое декодирование.

Вероятностные методы декодирования достаточно сложны в реализации, хотя иобеспечивают высокую помехоустойчивость. Наряду с ними широко применяют болеепростые алгоритмы. Для этой цели используют класс СК, допускающих пороговоедекодирование.

<img src="/cache/referats/3986/image062.gif" v:shapes="_x0000_s1051">
Рассмотримсистематический код со скоростью 1/2 и многочленами:

Схема кодека на рисунке. Моделью двоичного канала являются сумматоры по

модулю2, на входы которых, кроме кодовых последовательностей а(1)и а(2), поступают ошибки е(1)и е(2). Декодер содержит аналог кодера,в котором принятым символам формируетсякопия проверочной последовательности. В формирователе синдрома (сумматоре помодулю 2) образуется последовательность синдромов, которая поступает на входсиндромного регистра. Наборам ошибок соответствуют определенные конфигурациисиндромов последовательности S. Если количество ненулевыхсиндромов превышает определенный порог, на выходе порогового элементапоявляется символ коррекции, который в корректоре используется для исправленияошибки в информационном символе.

Список использованной литературы:

1.<span Times New Roman"">

Радиотехнические системы передачи информации, подред. В. В. Калмыкова

2.<span Times New Roman"">

Сверточныекоды в системах передачи информации, учебное пособие

еще рефераты

Еще работы по радиоэлектронике

Реферат по радиоэлектронике

Эффект Ганна и его использование, в диодах, работающих в генераторном режиме

29 Августа 2013

Реферат по радиоэлектронике

Лазерная безопасность