Теория кодирования

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

     1.4 Помехоустойчивые коды 

     1.4.1 Классификация помехоустойчивых кодов

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

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

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

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

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

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

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

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

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

     Физическая  среда, по которой передаются данные, не может быть абсолютно надёжной. Более того, уровень шума бывает очень высоким, например, в беспроводных системах связи и телефонных системах. Ошибки при передаче — это реальность, которую надо обязательно учитывать.[10]

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

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

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

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

     У групповых ошибок есть свои плюсы  и минусы. Плюсы заключаются в  следующем. Пусть данные передаются блоками по 1000 бит, а уровень ошибки 0,001 на бит. Если ошибки изолированные  и независимые, то 63% блоков будут содержать ошибки. Если же они возникают группами по 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 или наоборот. В таких каналах очень маловероятно, чтобы в одном блоке были переходы обоих видов, и поэтому почти все ошибки приводят к изменению веса блока, и, следовательно, обнаруживаются.

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