Кодирование информации в компьютере. Алгоритмы помехоустойчивости кодирования

Условимся называть алфавит, с помощью которого представляется информация до преобразования, первичным; алфавит конечного представления - вторичным.

Код - (1) правило, описывающее соответствие знаков или их сочетаний одного алфавита знакам или их сочетаниям другого алфавита.

Код - (2) знаки вторичного алфавита, используемые для представления знаков или их сочетаний первичного алфавита.

Кодирование - перевод информации, представленной посредством первичного алфавита, в последовательность кодов.

Декодирование - операция, обратная кодированию, т.е. восстановление информации в первичном алфавите по полученной последовательности кодов.

Операции кодирования и декодирования называются обратимыми, если их последовательное применение обеспечивает возврат к исходной информации без каких-либо ее потерь.

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

 

Представление символьной информации в компьютере:

Компьютерный алфавит должен включать:

ü 26 2=52 букв латинского алфавита (с учетом прописных и строчных);

ü 33 2=66 букв русского алфавита;

ü цифры 0…9 - всего 10;

ü знаки математических операций, знаки препинания, спецсимволы 20.

Получаем, что общее число символов N 148. Теперь можно оценить длину кодовой цепочки: K(2) log2148 7,21. Поскольку K(2)должно быть целым, очевидно K(2) = 8. Именно такой способ кодирования принят в компьютерных системах: любому символу ставится в соответствие цепочка из 8 двоичных разрядов (8 бит). Такая цепочка получила название байт, а представление таким образом символов - байтовым кодированием.

Байт наряду с битом может использоваться как единица измерения количества информации в сообщении. Один байт соответствует количеству информации в одном символе алфавита при их равновероятном распределении. Этот способ измерения количества информации называется также объемным.

Именно байт принят в качестве единицы измерения количества информации в международной системе единиц СИ. 1 байт = 8 бит. Использование 8-битных цепочек позволяет закодировать 28 = 256 символов, что превышает оцененное выше N.

Для совместимости технических устройств и обеспечения возможности обмена информацией между многими потребителями требуется согласование кодов. Подобное согласование осуществляется в форме стандартизации кодовых таблиц. В персональных компьютерах и телекоммуникационных системах применяется международный байтовый код ASCII (American Standard Code for Information Interchange - «американский стандартный код обмена информацией»). Он регламентирует коды первой половины кодовой таблицы (номера кодов от 0 до 127, т.е. первый бит всех кодов 0). В эту часть попадают коды прописных и строчных английских букв, цифры, знаки препинания и математических операций, а также некоторые управляющие коды (номера от 0 до 31). Ниже приведены некоторые ASCII-коды:

Знак, клавиша Код двоичный Код десятичный
пробел
A (лат)
B (лат)
Z
[Esc]
[Enter]

 

Вторая часть кодовой таблицы - она считается расширением основной - охватывает коды в интервале от 128 до 255 (первый бит всех кодов 1). Она используется для представления символов национальных алфавитов (например, русского или греческого), а также символов псевдографики. Для этой части также имеются стандарты, например, для символов русского языка это КОИ-8, КОИ-7 и др.

В настоящее время находит все более широкое применение еще один международный стандарт кодировки - Unicode. В нем использовано 16-битное кодирование, т.е. для представления каждого символа отводится 2 байта. Такая длина кода обеспечивает включения в первичный алфавит 65536 знаков. Это позволяет создать и использовать единую для всех распространенных алфавитов кодовую таблицу.

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

Код защиты по четности:

В данном коде существует информационная часть и контрольный разряд:

1010101 0

информационная часть контрольный разряд

Контрольный разряд определяется по следующему правилу: суммируется по модулю 2 количество единиц в информационной части: 1 1=0, 1 0=1. Если в информационной части количество единиц четно, то контрольный разряд равен 0. Если наоборот, то равен 1. Информационная часть выбирается так, чтобы количество единиц было четным. Если под действием помехи единица в одном из разрядов станет 0 или наоборот, то это будет обнаружено, т.е. однократная ошибка обнаруживается. Если два разряда меняются под действием помехи (двукратная ошибка), то она не обнаруживается. Ошибки нечетной кратности обнаруживаются. Ошибки четной кратности не обнаруживаются. Существуют кодовые комбинации разрешенные (четные) и запрещенные (нечетные). Защита от помехи заключается в распознавании запрещенной или разрешенной кодовой комбинации.

 

Коды с обнаружением и исправлением ошибок:

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

 

Коды Хемминга:

Идея кода Хемминга заключается в неоднократной проверке на четность (не менее трех раз). Простейший код Хемминга называется (7.4), где 7 - общее количество n; 4 - количество информационных разрядов nи. Количество контрольных разрядов: nk=n-nи.

Таблица формирования кода Хемминга:

… 8 7 6 5 4 3 2 1

к и и и к и к к

где к - контрольный разряд;

и - информационный разряд.

Место контрольного разряда определяется как 2i, где i=0,1,2…

Правило определения места контрольного разряда:необходимо вычисление контрольных сумм (сколько контрольных разрядов, столько и контрольных сумм S): S1=x1 x3 x5 x7 x9 … (суммируются нечетные разряды через один); S2=x2 x3 x6 x7 x10 x11 … (суммируются попарно через два); S3=x4 x5 x6 x7 x12 … (суммируются через четыре по четыре); S4=x8 x9 x10 x11 … x20 … (суммируются по восемь через восемь).

Если ошибки нет, то эти контрольные суммы должны быть равны нулю (S1=0,S2=0,S3=0 …). Отсюда вытекает правило выбора контрольных разрядов: x1=x3 x5 x7 … ; x2=x3 x6 x7 … ; x4=x5 x6 x7 … .

Обнаружение и исправление ошибок основано на вычислении контрольных сумм. Если S1=0, то ошибки нет в нечетных разрядах. Если S2=0, то ошибки нет в попарных разрядах. Опознаватель ошибок S составляется из контрольных сумм и записывается со старшего разряда:

S= S3S2S1

Если S=011, то ошибка в третьем разряде. Опознаватель ошибки дает номер ошибочного разряда. Для определения требуемого количества контрольных разрядов в коде Хемминга можно воспользоваться формулой:

n=2nk-1 , где n=nи+ nk

Если nk =3, то S=000÷111 , т.е. выявляется 7 видов ошибок и защищается 7 разрядов.

Если nk =4, то S=0000÷1111 , т.е. выявляется 15 видов ошибок и защищается 15 разрядов.

Группы циклических кодов:

Название «циклический код» означает, что при циклическом сдвиге кодовой комбинации получается новая комбинация, которая также принадлежит к этим кодам. Эту особенность используют для проверки правильности циклического кода. Обнаружение и исправление ошибок в этом коде связано с операцией деления на специальную кодовую операцию, образующую полином P(x).

Представление кодовой комбинации в виде полинома:

P(x)=10112=1*x3+0*x2+1*x1+1*x0=x3+x+1 - кодовая комбинация представленная в виде суммы степеней (в виде полинома). Здесь номер разряда - показатель степени. Если xi=0, то в сумме его опускают. Если xi=1, то показатель степени опускают. Деление полиномов является основной операцией по выявлению и исправлению ошибок. Оно схоже с обычным алгебраическим делением: вычитание заменяется суммированием по модулю 2. Если при делении полиномов получается остаток, то это признак ошибки, и кодовая комбинация не принадлежит к циклическому коду.

Формирование циклического кода:

1) Выбирается образующий полином. Чем больше количество разрядов P(x), тем больше корректирующая способность и большее количество разрядов можно защитить. Выбирается образующий P(x) из кодовой комбинации аналогично простому арифметическому числу (11,13,17,19,23…). Степень образующего полинома k-это номер старшего разряда кодовой комбинации. 1110=10112= P(x) k=3

2) Выбирается исходная кодовая комбинация Q(x), которую необходимо защитить от помех; например, безизбыточный код.

3) Сдвигаем эту кодовую комбинацию Q(x) влево на k разрядов.

4) Делим Q(x) *x k на образующий полином P(x).

5) Делим пока не получим остаток R(x).

6) Сложим Q(x) *x k R(x) по модулю 2.

7) Полученная кодовая комбинация будет циклическим кодом.

Формула формирования циклического кода: F(x)= Q(x) *x k R(x).

Выбор степени образующего полинома выбирается также как и для кода Хемминга: n=2k-1 или ni+k=2k-1 , где n - полное количество разрядов. Если k=3, то n=23-1=7 разрядов; если k=5, то n=25-1=31 разряд. Выгода защищать большое количество разрядов.

Обратная операция - проверка циклического кода сводится к обнаружению и исправлению возможной ошибки. Если k=3, то искажение одинарной ошибки обнаруживается и исправляется. Если искажено 2 разряда, то ошибка только обнаруживается. Если искажено 3 разряда, то она может быть не обнаружена.