Файл: Методы кодирования данных (Процесс формирования цифровых сигналов).pdf

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

Теория кодирования появилась в сороковых годах с появлением работ Голея, Хэмминга и Шеннона. Выдающиеся два ученые Голей и Хэмминг заложили базис алгебраическим техникам шифрования, которые применяются и в наше время, а Шеннон реализовал и исследовал понятие случайного кодирования. Важно заметить, что в актуальных информационных комплексах одной из важных проблем является практическая реализация информационной безопасности, связанной с методами криптографии и кодирования, теоретические базисы которой заложил Шеннон в своих работах.[3]

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

В 50-е-70-е годы было спроектировано и реализовано значительное число алгебраических кодов с поиском и исправлением ошибок, среди которых самыми удачными стали коды Боуза-Чоудхури-Хоквингема (БЧХ), Рида-Соломона (РС), Рида-Малера, Адамара, Юстенсена, Гоппы, циклические коды, сверточные коды с различными техниками декодирования (последовательное декодирование, алгоритм Витерби), арифметические коды.

Тем не менее, в практических реализациях используются довольно-таки малая группа алгебраических помехоустойчивых кодов: БЧХ, Рида-Соломона и сверхточные коды. Наиболее популярными являются циклические коды с обнаружением ошибок в стандартных протоколах HDLC, Х.25/2 (LAP-B, LAP-M). Коды Рида-Соломона с исправлением ошибок находят применение в каналах радиосвязи. В каналах спутниковой связи, которым свойственны независимые характеры возникающих ошибок, часто используются сверхточные коды .

Следует отметить тот факт, что хотя существующие на данный момент системы передачи данных отвечают всем основным стандартам и требованиям, они все же не являются совершенными. Причин тому влияние помех в канале связи. Одним из средств решения подобных несоответствий в системах передачи цифровой информации, является применение помехоустойчивых кодов, лежащих в основе устройств кодирования/декодирования.

Помехоустойчивое кодирование передаваемой информации позволяет в приемной части системы обнаруживать и исправлять ошибки. Коды, применяемые при помехоустойчивом кодировании, называются корректирующими кодами. Как правило, корректирующий код может исправлять меньше ошибок, чем обнаруживать. Число ошибок, которые корректирующий код может исправить в определенном интервале последовательности двоичных символов, например, в одной кодовой комбинации, называется исправляющей способностью кода.

Данные передаются в реальной физической среде, а она изначально не может быть 100% надежной. Кроме того, шумовой уровень также может быть довольно-таки большим. Ошибки при передаче данных – это реальные условия, которые следует непременно учитывать в расчетах.

Разные физические среды предполагают различных уровень и характер помех. Могут возникать как одиночные ошибки, так и по группам или даже несколькими блоками. Таким образом в ходе передаче теряются биты информации или же, напротив, появляются новые ошибочные биты.

Главным свойством интенсивности помех на линии связи является переменная шума — p. Это значения от 0 до 1, равное вероятности инвертирования бита данных.

Другая переменная величина— p2. Это вероятность того же события, но при условии, что предыдущий бит также был инвертирован.

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

У групповых ошибок есть свои достоинства и недостатки. Пусть информация транслируется блоками по 1000 бит, а параметр ошибки 0,001 на бит. Если ошибки изолированные и независимые, то 60% блоков будут включать в себя ошибки. Если же они появятся группами по 100 сразу, то ошибки будут включать в себя 1% блоков.

Если же ошибки не группируются, то в любом кадре они малы, и их можно устранить. Групповые ошибки портят кадр безвозвратно. Требуется его повторная пересылка, но в некоторых системах это в принципе невозможно, — например, в телефонных системах, использующие цифровое кодирование, возникает эффект пропадания слов/слогов.

Для надёжной передачи кодов было предложено два основных метода.

Первый — добавить в передаваемый блок данных нескольких «лишних» бит так, чтобы, анализируя полученный блок, можно было бы сказать, есть в переданном блоке ошибки или нет. Это, так называемые, коды с обнаружением ошибок.

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

Под помехой понимается любое воздействие, накладывающееся на полезный сигнал и затрудняющее его прием.

Внешние источники помех вызывают в основном импульсные помехи, а внутренние - флуктуационные. Помехи, накладываясь на видеосигнал, приводят к двум типам искажений: краевые и дробления. Краевые искажения связаны со смещением переднего или заднего фронта импульса. Дробление связано с дроблением единого видеосигнала на некоторое количество более коротких сигналов. [4]

Помехоустойчивые коды делятся на блочные и непрерывные.

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

Непрерывные или рекуррентные коды образуют последовательность символов, не разделяемую на отдельные кодовые комбинации. Кодирование и декодирование непрерывно совершаются над последовательностью элементов без деления их на блоки. Формирование проверочных символов ведётся по рекуррентным (возвратным) правилам, поэтому непрерывные коды часто называют рекуррентными или цепными.

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

К непрерывным кодам относятся и свёрточные коды, в которых каждый информационный символ, поступающий на вход кодирующего устройства, вызывает появление на его выходе ряда проверочных элементов, образованных суммированием по модулю 2 данного символа и " k-1 " предыдущих информационных символов. Рекуррентные коды позволяют исправлять групповые ошибки (" пачки ") в каналах связи.

Блочные коды делятся на равномерные и неравномерные. В равномерных кодах, в отличие от неравномерных, все кодовые комбинации содержат одинаковое число n - символов (разрядов) с постоянной длительностью τ0 импульсов символов кода. Равномерные коды в основном и применяются в системах связи, так как это упрощает технику передачи и приёма.

Классическими примерами неравномерного кода являются код Морзе, широко применяемый в телеграфии, и код Хафмена, применяемый для компрессии информации (факсимильная связь, ЭВМ).

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

Почти все блочные корректирующие коды принадлежат к разделимым кодам, в которых кодовые комбинации состоят из двух частей: информационной и проверочной. Их символы всегда занимают одни и те же позиции, т.е. располагаются на определённых местах. Как правило, в таких кодах, все кодовые комбинации которых содержат n символов, первые k символов являются информационными, а за ними располагаются (n - k) проверочных символов. В соответствии с этим разделимые коды получили условное обозначение – (n , k) - коды.

В неразделимых кодах деление на информационные и проверочные символы отсутствует. К таким кодам относятся, в частности, коды с постоянным весом, так называемые равновесные коды. Например, Международным Консультативным Комитетом по телеграфии и телефонии (МККТТ) рекомендован для использования телеграфный код № 3 - семиразрядный код с постоянным весом, т.е. с числом единиц в каждой кодовой комбинации, равным 3 (W = 3).

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

Так как теоретическим базисом реализации такого рода совокупностей является математический аппарат линейной алгебры, то коды также именуются линейными. Блочные равномерные разделимые линейные коды содержат проверочные знаки, которые создаются по конкретным правилам, поэтому они носят название «систематические».

Использование аппарата линейной алгебры, в которой существенное значение имеет понятие "группа", породило и другое название этих типов кодов - групповые.

Эти коды получили наибольшее применение в системах передачи дискретной информации.

Несистематические (нелинейные) коды не характеризуются приведенными выше характеристиками, таким образом они используются существенно менее часто и только в специфических ситуациях. Удачным образцом нелинейного кода можно считать вышеупомянутый равновесный неразделимый код. Коды данного типа, как правило, применяются в асимметричных линиях связи, которые характеризуются вероятностью перехода «1 => 0» существенно больше вероятности перехода «0=>1» или в обратном порядке. В таких типах линии связи крайне маловероятно, чтобы в одном сегменте сосуществовали переходы двух типов, а, значит, практически все ошибки ведут к модификации веса сегмента, и, таким образом, достаточно эффективно обнаруживаются.

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

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

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

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

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

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

Проверочная группа из r знаков создается посимвольно по определенному алгоритму. Коды Хемминга, имеющие dmin = 3, дают возможность исправить одну ошибку

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