Васин В.И. Информационные технологии в радиотехнических системах. Под ред. И.Б.Федорова (2003) (1092038), страница 112
Текст из файла (страница 112)
Подобные кодеки находят применение и при передаче подвижных и неподвижных изображений в цифровых телевизионных каналах. При помехоустойчивом кодировании в поток передаваемых символов вводятся дополнительные (избыточные) символы для исправления возникающих на приемной стороне ошибок. Это требует увеличения скорости 572 9.5, Помехоуетойчивое кодирование и декодирование передачи по каналу, что при выбранном типе модема эквивалентно расши рению полосы частот сигнала и уменьшению энергии посылки. Поэтому может возникнуть правомерный вопрос о целесообразности использования вообще избыточного кодирования.
На этот вопрос дает ответ теорема Шеннона о пропускной способности непрерывного канала связи, из которой следует, что пропускная способность непрерывного канала увеличивается с расширением его полосы, но при оптимальном в широком смысле кодировании. Поэтому следует ожидать повышения достоверности передачи при заданной скорости и отношении сигнал †ш в канале при внесении избыточности. Однако ответа на вопрос «каким должен быть оптимальный кодек?» нет, да и, наверное, для сообщения, не фиксированного по длительности, не может быть.
Тем не менее, избыточное кодирование широко используется для повышения верности передачи особенно в последние десятилетия, когда проблема создания сложных вычислительных устройств в малых габаритах практически решена. Рассмотрим принципы кодирования на примере двоичного канала. Допустим, что источник обладает максимальной производительностью. Тогда обязательным условием внесения избыточности является увеличение числа переданных посылок за единицу времени по сравнению с их числом, поступающим от источника.
Как вносятся избыточные символы, определяет тип кода. Наиболее просто предположить, что группе из /с символов источника ставится в соответствие п символов, передаваемых по каналу. Такой код называется блочным и записывается условно как (л, 7г)-код. Возможны непрерывные коды, которые характеризуются тем, что операции кодирования и декодирования производятся над непрерывной последовательностью символов без разбиения ее на блоки. Рассмотрим принципы помехоустойчивого кодирования на примере блочного двоичного кода как наиболее простого [11, 132~.
Если к символам источника добавляются избыточные символы, то код называют систематическим. Если группе информационных символов ставится в соответствие новая группа символов, передаваемая по каналу, в которой информационных символов в явном виде нег, то код называется неразделимым. Теперь ответим на основной вопрос: как строить кодек, чтобы при фиксированной избыточности 11 = г(п, где г — число проверочных символов для разделимого кода, достоверность передачи была бы максимальной? При передаче безызбыточным примитивным кодом с числом разрядов 1с в каждом слове все Фр = 2" комбинаций являются разрешенными и ошибка хотя бы в одном символе приводит к тому, что одна разрешенная комбинация переходит в другую и происходит ошибка в приеме сообщения.
Введение избыточных символов приводит к тому, что полное число комбинаций увеличивается и становится равным Ф = 2", причем часть из них 573 9. Радиотехнические системы передачи информации )У- Фр являются запрещенными и могут возникать только тогда, когда в канале происходят ошибки. Этот факт положен в основу обнаружения и исправления ошибок. Введем понятие кодового расстояния.
Предварительно отметим, что для оценки отличия одной кодовой комбинации от другой можно использовать расстояние Хэмминга еЧФ„Л~), определяемое числом разрядов, в которых одна кодовая комбинация отличается от другой. Для двоичного кода где Ьа н Ьд — lс-е символы кодовых комбинаций Л~, и М; соответственно; Ю вЂ” символ суммирования по модулю 2, Наименьшее расстояние Хэмминга для данного кода называется кодовым расстоянием. В дальнейшем его будем обозначать через с1 При независимых ошибках в канале корректирующую способность кода удается выразить через кодовое расстояние.
Пусть имеется код с Ы = 1. Учитывая, что искажение одного символа изменяет расстояние Хэмминга на одну единицу, при применении кода с И = 1 обнаруживаются не все одиночные ошибки. Для того чтобы код мог обнаруживать любую одиночную ошибку, необходимо обеспечить кодовое расстояние, равное двум. Рассуждая аналогичным образом, получаем, что для обнаружения всех ошибок кратности 1требуется код с Для исправления всех ошибок некоторой кратности требуется большее кодовое расстояние„чем для их обнаружения. Если кратность исправляемых ошибок равна 1, то кодовое расстояние должно удовлетворять условию И > 21+ 1.
Очевидно, что кодовое расстояние между разрешенными комбинациями можно сделать тем больше, чем больше избыточность. Однако при этом уменьшается длительность посылок и возрастает вероятность ошибок при их приеме. Поэтому вводят понятие эффективности избыточного кодиРования как отношение вероятностей ошибочного приема кодовой комбинации из к информационных символов при передаче нх примитивным и избыточным кодами: с = Р(/с)!Р(п,/с). Если код примитивный, то ошибка возникает, если хотя бы в одном символе при приеме произошла ошибка. Вероятность такого события равна 574 9.5. Помекоуетойчивое кодирование и декодирование Р(/г)=1 — (1 — Р, „) мИ', где Р „— вероятность ошибки в приеме одного символа при передаче сообщения примитивным кодом. Для избьггочного кода ошибка в приеме кодовой комбинации будет иметь место тогда, когда число ошибок превысит исправляющую способность кода /„и ее вероятность Р(н,/г)= ,') С„'Р,' „(1-Р, „)" ' 1=им где Р,,„— вероятность ошибки в приеме одного символа при передаче избыточным кодом.
Различие в Р „и Р, „определяется уменьшением длительности посылки при передаче избыточным кодом, пропорциональной отношению /г/и. Величины Р „и Р, „могут быть найдены, если известен вид модуляции и демодуляции, отношение Р /И, и длительность посылок источника. Таким образом, задача построения кода с заданной корректирующей способностью сводится к обеспечению необходимого кодового расстояния при введении избыточности. При этом желательно, чтобы число используемых проверочных символов было минимальным.
К сожалению„ задача определения минимального числа проверочных символов, необходимых для обеспечения заданного кодового расстояния, не решена. Имеется лишь ряд оценок для максимального кодового расстояния при фиксированных и и /с, которые часто используются при выяснении того, насколько построенный код близок к оптимальному, Можно показать (1331, что если существует блочный линейный код (и, А), то для него справедливо неравенство (9.8) г) 1о8 ) С„' называемое верхней границей Хэмминга, где ((о/ — 1)/21 означает целую часть числа (е/- 1)/2.
Граница Хэмминга (9.8) близка к оптимальной для кодов с большими значениями к/н. Для кодов с малыми значениями к/н более точной является верхняя граница Плоткина: г ~ 2Ы вЂ” 2 — 1ойг(о/). Можно также показать, что существует блочный линейный код (п, /е) с кодовым расстоянием е/, для которого справедливо неравенство 575 9. Радиотехнические системы передачи информации называемое нижней границейВаршамова — Гильберта. Таким образом, границы Хэмминга и Плоткина являются необходимыми условиями существования кода, а граница Варшамова — Гильберта— достаточным.
Эти границы позволяют оценить эффективность блочных кодов и целесообразность их применения, 9.5.2. Линейные блочные коды Линейный (и, lс)-код можно получить из lс линейно независимых кодовых комбинаций путем их посимвольного суммирования по модулю 2 в различных сочетаниях. Исходные линейно независимые кодовые комбинации называются базисными. Представим базисные кодовые комбинации в виде (пк7с)-матрицы ьн %2 "' К!» в21 в22 "' 02» в»1 Я»2 "' в»» (9.9) В теории кодирования матрица С называется порождающей. Тогда процесс кодирования заключается в выполнении операции В=АС, где А — вектор размерности lс, соответствующий сообщению;  — вектор размерности и, соответствующий кодовой комбинации.
Таким образом, порождающая матрица (9.9) содержит всю необходимую для кодирования информацию. Она должна храниться в памяти кодиРуклцего устройства. Для двоичного кода объем памяти равен «кп двоичных символов. При табличном задании кода кодирующее устройство должно запоминать и 2 двоичных символов. Две порождающие матрицы, отличающиеся друг от друга только поРядком расположения столбцов, задают коды, которые имеют одинаковые расстояния Хэмминга между соответстствующнмн кодовыми комбинациями, а следовательно„одинаковые корректирующие способности. Такие коды называются эквивалентными.
В качестве базисных комбинаций часто выбирают кодовые комбинации, содержащие по одной единице среди информационных символов. При этом порождающую матрицу (9.9) удается записать в канонической форме: 576 9.5, Помекоуотойчивое кодирование и декодирование 100...00 ~„,, 010...00 (9.10) где 1 — единичная (Ус к Уг)-подматрица; Р— (к к (77 — lг))-подматрица проверочных символов, определяющая свойства кода. Матрица (9.10) задает систематический разделимый код. Можно показать, что для любого линейного кода существует эквивалентный систематический код.
Линейный (и, к)-код может быть задан так называемой проверочной матрицей Н размерности г к и. При этом некоторая комбинация В принадлежит коду только в том случае, если вектор В ортогонален всем строкам матрицы Н, т. е. если выполняется равенство ВН' =О, (9.1 1) где т — символ транспонирования матрицы. Поскольку равенство (9.11) справедливо для любой кодовой комбинации, то Каноническая форма матрицы Н имеет вид е К ... е 100...00 д2~„2 ... дц 2 010...00 (9.12) д 000...01 где Р' — подматрица, столбцами которой служат строки подматрицы Р из соотношения (9.10); 1 — единичная (г к 1)-подматрица. Подставляя (9. 12) в (9.11), можно получать п — lг уравнений вида Ь8„9,'~ ЮК,„7Ь1 =О, 5'=1,2, ...,п — 18, (9.13) 577 20 — 78! 6 которые называются уравнениями проверки.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
