Исследование помехоустойчивых кодов (Исследование помехоустойчивых кодов (лабораторная работа №3))

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ1. Принципы построения кодековКодированием и декодированием в широком смысле называют любоепреобразование сообщения в сигнал и, обратно, сигнала в сообщение путем установлениявзаимного соответствия. Преобразование следует считать оптимальным, если в итогепроизводительность источника и пропускная способность непрерывного канала окажутсяравными, т.

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

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

Тогдадля его передачи по радиоканалу с выбранным модемом потребуется минимальная полосачастот. Не рассматривая методы экономного кодирования, укажем только основныесвойства дискретного сигнала, в котором полностью устранена избыточность, — это равнаявероятность и независимость их появления в последовательности. В этом случае среднееколичество информации на символ равно log2 m.Примером экономного кодирования является передача речевого сигнала поцифровым каналам. Если ориентироваться только на смысловое (информационное)содержание, то можно перейти к передаче текста со скоростью 5…10 букв в секунду. Сучетом объема алфавита в двоичном канале это потребует скорость передачи 25…50 бит/с.Если устранить избыточность, связанную с неодинаковой вероятностью их появления и ихкорреляцией в тексте, то, как показывают расчеты, скорость передачи может бытьуменьшена до 10 бит/с.

Если предавать речь в цифровой форме, используя аналоговоцифровое преобразование, ориентируясь только на ширину спектра и динамическийдиапазон, то скорость потока двоичных символов составит 32…64 кбит/с. Такаяколоссальная избыточность привела к необходимости разработки специальных кодековречевых сигналов, называемых вокодерами, которые нашли применение при передачеречи в цифровой форме по радиоканалам. Например, в сотовых системах мобильнойсвязи стандарта GSM скорость передачи составляет 8,5 кбит/с, причем сохраняется нетолько смысловое содержание, но и индивидуальные особенности говорящего.Подобные кодеки находят применение и при передаче подвижных и неподвижныхизображений в цифровых телевизионных каналах.При помехоустойчивом кодировании в поток передаваемых символов вводятсядополнительные (избыточные) символы для исправления возникающих на приемнойстороне ошибок.

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

Поэтому следует ожидатьповышения достоверности передачи при заданной скорости и отношении сигнал—шум вканале при внесении избыточности. Однако ответа на вопрос: каким должен бытьоптимальный кодек? — нет, да и, наверное, для сообщения, не фиксированного подлительности, не может быть. Тем не менее, избыточное кодирование широко используетсядля повышения верности передачи особенно в последние десятилетия, когда проблемасоздания сложных вычислительных устройств в малых габаритах практически решена.Рассмотрим принципы кодирования на примере двоичного канала. Допустим, чтоисточник обладает максимальной производительностью.

Тогда обязательным условиемвнесения избыточности является увеличение числа переданных посылок за единицувремени по сравнению с их числом, поступающим от источника. Как вносятся избыточныесимволы, определяет тип кода. Наиболее просто предположить, что группе из k символовисточника ставится в соответствие n символов, передаваемых по каналу. Такой кодназывается блочным и записывается условно как (n, k)-код. Возможны непрерывные коды,которые характеризуются тем, что операции кодирования и декодирования производятсянад непрерывной последовательностью символов без разбиения ее на блоки.Рассмотрим принципы помехоустойчивого кодирования на примере блочногодвоичного кода как наиболее простого [11, 132]. Если к символам источника добавляютсяизбыточные символы, то код называют систематическим.

Если группе информационныхсимволов ставится в соответствие новая группа символов, передаваемая по каналу, вкоторой информационных символов в явном виде нет, то код называется неразделимым.Теперь ответим на основной вопрос: как строить кодек, чтобы при фиксированнойизбыточности  = r/n, где r — число проверочных символов для разделимого кода,достоверностьпередачибылабымаксимальной?Припередачебезызбыточным примитивным кодом с числом разрядов k в каждом слове все Nр = 2kкомбинаций являются разрешенными и ошибка хотя бы в одном символе приводит к тому,что одна разрешенная комбинация переходит в другую и происходит ошибка в приемесообщения.Введение избыточных символов приводит к тому, что полное число комбинацийувеличивается и становится равным N = 2n, причем часть из них N – Nр являютсязапрещенными и могут возникать только тогда, когда в канале происходят ошибки.

Этотфакт положен в основу обнаружения и исправления ошибок.Введем понятие кодового расстояния. Предварительно отметим, что для оценкиотличия одной кодовой комбинации от другой можно использовать расстояние Хэммингаd(Ni, Nj), определяемое числом разрядов, в которых одна кодовая комбинация отличаетсяот другой. Для двоичного кодаnd  N i , N j    bik  b jk ,k 1где bik и bjk — k-e символы кодовых комбинаций Ni и Nj соответственно; — символ суммирования по модулю 2. Наименьшее расстояние Хэмминга для данногокода называется кодовым расстоянием. В дальнейшем его будем обозначать через d.При независимых ошибках в канале корректирующую способность кода удаетсявыразить через кодовое расстояние. Пусть имеется код с d = 1.

Учитывая, что искажениеодного символа изменяет расстояние Хэмминга на одну единицу, при применении кода с d= 1 обнаруживаются не все одиночные ошибки. Для того чтобы код мог обнаруживатьлюбую одиночную ошибку, необходимо обеспечить кодовое расстояние, равное двум.Рассуждая аналогичным образом, получаем, что для обнаружения всех ошибок кратности lтребуется код с≥ +1Для исправления всех ошибок некоторой кратности требуется большее кодовоерасстояние, чем для их обнаружения. Если кратность исправляемых ошибок равна l, то кодовоерасстояние должно удовлетворять условию≥2 +1Очевидно, что кодовое расстояние между разрешенными комбинациями можносделать тем больше, чем больше избыточность.

Однако при этом уменьшаетсядлительность посылок и возрастает вероятность ошибок при их приеме. Поэтому вводятпонятие эффективности избыточного кодирования как отношение вероятностейошибочного приема кодовой комбинации из k информационных символов при передаче ихпримитивным и избыточным кодами:  P (k ) / P (n, k ).Если код примитивный, то ошибка возникает, если хотя бы в одном символе приприеме произошла ошибка. Вероятность такого события равнаP (k )  1  (1  Pош.п ) k  kPош.п ,где Pош.п — вероятность ошибки в приеме одного символа при передаче сообщенияпримитивным кодом.Для избыточного кода ошибка в приеме кодовой комбинации будет иметь местотогда, когда число ошибок превысит исправляющую способность кода tи и ее вероятностьP ( n, k ) niCni Pош.и(1  Pош.и ) n ii tи 1где Pош.и — вероятность ошибки в приеме одного символа при передаче избыточнымкодом.Различие в Pош.п и Pош.и определяется уменьшением длительности посылки припередаче избыточным кодом, пропорциональной отношению k/n.

Величины Pош.п и Pош.имогут быть найдены, если известен вид модуляции и демодуляции, отношение Рс/No идлительность посылок источника.Таким образом, задача построения кода с заданной корректирующей способностьюсводится к обеспечению необходимого кодового расстояния при введении избыточности.При этом желательно, чтобы число используемых проверочных символов быломинимальным.

К сожалению, задача определения минимального числа проверочныхсимволов, необходимых для обеспечения заданного кодового расстояния, не решена.Имеется лишь ряд оценок для максимального кодового расстояния при фиксированных п иk, которые часто используются при выяснении того, насколько построенный код близок коптимальному.Можно показать [133], что если существует блочный линейный код (п, k), то для негосправедливо неравенство ( d 1)/2 r  log 2   Cni  , i 0(9.8)называемое верхней границей Хэмминга, где [(d – 1)/2] означает целую часть числа(d – 1)/2.Граница Хэмминга (9.8) близка к оптимальной для кодов с большими значениямиk/n. Для кодов с малыми значениями k/n более точной является верхняя граница Плоткина:r ≥ 2d – 2 – log2 (d).Можно также показать, что существует блочный линейный код (п, k) с кодовымрасстоянием d, для которого справедливо неравенство d 2 r  log 2   Cni  , i 0 называемое нижней границей Варшамова—Гильберта.Таким образом, границы Хэмминга и Плоткина являются необходимыми условиямисуществования кода, а граница Варшамова—Гильберта — достаточным.

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

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