Кодирование информации. Помехозащищенные коды
Код - набор условных обозначений для представления информации. Кодирование - процесс представления информации в виде кода. Кодирование сводится к использованию совокупности символов по строго определенным правилам. При переходе улицы мы встречаемся с кодированием информации в виде сигналов светофора. Водитель передает сигнал с помощью гудка или миганием фар. Кодировать инфор-мацию можно устно, письменно, жестами или сигналами любой другой природы. Кодирование информации — процесс преобразования сигнала из формы, удобной для непосредственного использования информации, в форму, удобную для передачи, хранения или автоматической переработки.
Кодирование информации в двоичном коде .Вся информация кодируется в двоичной системе счисления: с помощью цифр 0 и 1. Эти два символа называют двоичными цифрами или битами. Такой способ кодирования технически просто организовать: 1 - есть электрический сигнал, 0 - нет сигнала. Недостаток двоичного кодирования - длинные коды. Но в технике легче иметь дело с большим числом простых однотипных элементов, чем с небольшим числом сложных.
Помехоустойчивое кодирование сообщений дает возможность обнаружить ошибки в принятых сообщениях или обнаруживать и исправлять их. Коды, обнаруживающие или исправляющие ошибки, называются помехоустойчивыми или корректирующими.Коды с обнаружением ошибок. Код с четным числом единиц Код содержит лишь один избыточный символ. Выбирается избыточный символ таким образом, чтобы общее количество единиц в кодовой комбинации было четным. Проверка кодовой комбинации производится путем суммирования по модулю два всех его символов. Код позволяет обнаруживать однократные ошибки и все ошибки нечетной кратности, так как только в этих случаях количество единиц в комбинации станет нечетным. Не обнаруживаются ошибки четной кратности. Код с удвоением элементов Код с удвоением элементов характеризуется введением дополнительных символов для каждого символа информационной части комбинации, причем единица дополняется нулем и преобразуется в 10, а нуль дополняется единицей и преобразуется в 01. Тогда исходная, например, комбинация 10101 будет представлена в виде 1001100110. Показателем искажения кода будет появление в «парных» элементах сочетаний вида 00 или 11. Избыточность кода не зависит от числа элементов кодовой комбинации и равна Кизб = 0,5. Код позволяет обнаруживать все ошибки, за исключением случаев, когда имеют место две ошибки в «парных» элементах. Помехоустойчивость кода с удвоением элементов выше помехоустойчивости кода с четным числом единиц. Это достигнуто за счет увеличения избыточности кода и усложнения процедуры проверки кода. Инверсный код В основу построения инверсного кода положен метод повторения исходной кодовой комбинации. Причем в тех случаях, когда исходная комбинация содержит четное число единиц, вторая комбинация в точности воспроизводит исходную. Если же исходная комбинация содержит нечетное число единиц, то повторение производится в инвертированном виде. Например, комбинации 01010 и 01110 инверсным кодом представляются соответственно как 0101001010 и 0111010001. Проверка кодовой комбинации производится в такой последовательности. Сначала суммируются единицы, содержащиеся в основной комбинации. Если их число окажется четным, то элементы дополнительной комбинации принимаются в неизменном виде. После этого обе комбинации сравниваются поэлементно (первый элемент с первым, второй со вторым и т. д.), и при обнаружении хотя бы одного несовпадения принятая комбинация бракуется. Если же количество единиц основной комбинации нечетное, элементы второй комбинации принимаются в инвертированном виде. Затем, как и в предыдущем случае, основная и дополнительная комбинации сравниваются поэлементно. Избыточность кода не зависит от числа элементов кодовой комбинации и равна Kизб = 0,5. Код позволяет обнаружить практически все ошибки в комбинации. Ошибки не будут обнаружены лишь тогда, когда одновременно исказятся два, четыре и т. д. элемента в исходной комбинации и соответствующие два, четыре и т. д. элемента дополнительной комбинации. Из рассмотренных кодов инверсный код обладает наибольшей помехоустойчивостью. Код с постоянным числом единиц и нулей в комбинациях (код с постоянным весом) Весом называется число единиц, содержащихся в кодовых комбинациях. Если число единиц во всех комбинациях кода будет постоянным, то такой код будет кодом с постоянным весом. Коды с постоянным весом относятся к классу блочных неразделимых кодов, поскольку здесь невозможно выделить информационные и проверочные символы. Наибольшее применение получили коды «3 из 7», «3 из 8», хотя возможны другие варианты. Первая цифра указывает на вес кода, вторая - на общее число символов в комбинации. Разрешенными комбинациями кода «3 из 7» являются такие, которые содержат три единицы независимо от их места в комбинации, например 1110000 или 1010100 и т.д. Обнаружение ошибок сводится к определению их веса. Если вес отличается от заданного, то считается, что произошла ошибка. Код обнаруживает веса ошибок нечетной кратности и части ошибок четной кратности. Не обнаруживаются ошибки, при которых несколько единиц превращается в нули и столько же нулей - в единицы (ошибки смещения), так как при этом вес кода не изменяется. В коде «3 из 7» возможных комбинаций сто двадцать восемь (=128), а разрешенных кода только тридцать пять. Распределительный код Сln Распределительный код Это также разновидность кода с постоянным весом, равным единице. В любой кодовой комбинации содержится только одна единица. Число кодовых комбинаций в распределительном коде Кодовые комбинации при n=6 можно записать в виде 000001,000010,000100,001000,010000,100000. Сложение по модулю 2 двух комбинаций показывает, что они отличаются друг от друга на кодовое расстояние d=2. Код с проверкой на четность Недостатком кода с четным числом единиц является необнаружение четных групповых ошибок. Этого недостатка лишены коды с проверкой на четность, где комбинации разбиваются на части, из них формируется матрица, состоящая из некоторого числа строк и столбцов: Строки образуются последовательно по мере поступления символов исходного кода. Затем после формирования т строк матрицы производится проверка на четность ее столбцов и образуются контрольные символы . Контрольные символы образуются путем суммирования по модулю 2 информационных символов, расположенных в столбце: . При таком кодировании четные групповые ошибки обнаруживаются. Не обнаруживаются лишь такие ошибки, при которых искажено четное число символов в столбце. Можно повысить обнаруживающую способность кода путем одновременной проверки на четность по столбцам и строкам или столбцам и диагоналям (поперечная и диагональная проверка). Если проверка проводится по строкам и столбцам, то код называется матричным. Проверочные символы располагаются следующим образом: ; . В этом случае не обнаруживаются только ошибки четной кратности с кратностью 4, 8, 16 и т.д., при которых происходит искажение символов с попарно одинаковыми индексами строк столбцов. Наименьшая избыточность кода получается в том случае, когда образуемая матрица является квадратной. Недостатком такого кода является необходимость внесения задержки в передачу информации на время, необходимое для формирования матрицы. Матричный код позволяет исправлять одиночные ошибки. Ошибочный элемент находится на пересечении строки и столбца, в которых имеется нарушение четности. Код с числом единиц, кратным трем Этот код образуется добавлением к k информационным символам двух дополнительных контрольных символов (m=2), имеющих такие значения, чтобы сумма единиц, посылаемых в линию кодовых комбинаций, была кратной трем. Код с удвоением элементов (корреляционный код) Элементы данного кода заменяются двумя символами, единица ‘1’ преобразуется в 10, а ноль ‘0’ в 01. Вместо комбинации 1010011 передается 10011001011010. Ошибка обнаруживается в том случае, если в парных элементах будут одинаковые символы 00 или 11 (вместо 01 и 10). Например, при k=5, n=10 и вероятности ошибки , . Но при этом избыточность будет составлять 50% Коды Хемминга Коды Хэмминга (Hamming codes) — это простой класс блочных кодов, которые имеют следующую структуру: , где m= 2,3,… Минимальное расстояние этих кодов равно 3, поэтому они способны исправлять вес однобитовые ошибки или определять все ошибочные комбинации из двух или менее ошибок в блоке. Декодирование с помощью синдромов особенно хорошо подходит к кодам Хэмминга. Фактически синдром можно превратить в двоичный указатель местоположения ошибки. Хотя коды Хэмминга не являются слишком мощными, они принадлежат к очень ограниченному классу блочных кодов, называемых совершенными.