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

Системы счисления, в которых  любое число получается путем  сложения или вычитания базисных чисел, называются аддитивными.

Унарная система – это  система счисления, в которой  для записи чисел используется только один знак – 1. Следующее число получается из предыдущего добавлением новой 1; их количество (сумма) равно самому числу.

3.1.  Позиционные  системы счисления.

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

0,1,2,3,4,5,6,7,8,9.

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

Рассмотрим число, записанное в десятичной системе: 343,32. В его  записи цифра 3 повторена три раза, при этом:

- левая цифра 3 означает  количество сотен (ее вес равен  102);

- цифра 3, стоящая перед  точкой, означает количество единиц (ее вес 10˚);

- самая правая цифра  3 означает количество десятых  долей единицы (ее вес равен  10-1).

Последовательность цифр 343,32 представляет собой сокращенную  запись выражения:

3·102+4·101+3·100+3·10-1+2·10-2

Десятичная запись любого числа Х в виде последовательности цифр имеет общий вид:

А=

 или другая форма:

 А=,

где: – цифры, q – основание системы счисления.

Запись числа в таком  виде представляет собой полином, где  каждый коэффициент ai, - цифра и i=0,1,2,…n/

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

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

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

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

Например, основанием десятичной системы счисления является число 10; двоичной – число 2; троичной –  число 3 и т.д

Для записи произвольного  числа в q – ричной системе счисления достаточно иметь q разных цифр , i=1,2,…,qю Так, в троичной системе счисления любое число, может быть выражено посредством цифр 0,1,2.Эти цифры служат для обозначения некоторых различных целых чисел, называемых базисными.

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

Для установления факта, что  число записано не в десятичной системе, около этого числа пишется  нижний индекс, указывающий основание  системы счисления :35.548 или 101(2).

 

2. Смешанные системы счисления.

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

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

Правило записи чисел в  смешанной системе счисления.

1. Все цифры системы с первичным основанием (вернее числа им

соответствующие),записываются с помощью цифр вторичного основания.

2. Устанавливается максимальное число разрядов в таковых записях и

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

3. Все цифры в первоначальной записи числа, заменяются наборами 

цифр , им соответствующим  записям вторичного основания.

4. Если в начале записи числа окажутся нули (слева от старшего

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

 

3. Двоичная система счисления

Для представления информации в ЭВМ используется двоичная система  счисления или, как говорят, применяется  двоичное кодирование. Основание двоичной системы q=2, алфавит ее состоит, соответственно, из двух цифр: 0 и 1.Двоичное кодирование или двоичный код имеет ряд достоинств, например.

• простота в обращении, так как используется всего два символа 0 и 1;
• соответствие этих символов   техническим характеристикам

цифровых схем, также имеющих  два устойчивых состояния :рабочее (1) и нерабочие (0).

Многие явления природы  и техники описываются, также  двумя состояниями: есть – нет, включен  – выключен, проходит (ток, сигнал) –  не проходит и др.

Символы 0 и 1 позволяют кодировать логических понятий «истина» (1) и  «ложь» (0).

В двоичной записи каждый разряд несет свою единицу информации и  называется битом [5,с.143-160].

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

Несмотря на преимущества двоичной системы счисления,ее недостаток – громоздкая форма записи двоичного  слова. Поэтому в ЭВМ нашли  применение и другие системы счисления.

Шестнадцатеричная система  счисления, система счисления с  основанием q=16(16=24) дает самую компактную запись числа ЭВМ. Для перевода двоичного числа в эту систему разбивают двоичную запись на четверки (титры) и заменяют их соответствующим эквивалентам в шестнадцатеричной системе, пользуясь таблицей перевода.

При чтении чисел в иных, не десятичных, системах счисления  принято называть отдельно каждую цифру. Сравним: 2510 – это двадцать пять, но258 читается как два – пять. В ЭВМ самостоятельно осуществляется перевод чисел из одной системы  счисления в другую.

Проблема отношения между основанием системы счисления (мощностью алфавита) и длиной получившегося слова связана с законом обратной зависимости объема и содержания. Обратим внимание на следствие этого в лингвистике. В последнее время встала проблема поиска оптимального алфавита, обострившаяся в связи с попытками перевести письменность некоторых народов кириллицы (33 литеры) на латинский алфавит (26 знаков). Считается, что 32 – 33 знака являются оптимальным объемом алфавита и для запоминания, и для написания и произношения слов. На этой же причине, системы счисления с основанием q=10 – 16, являются оптимальными. Десятичная – наиболее употребляемой из них.

 

4. Современные способы кодирования
1. Алфавитное кодирование

Не равномерное  кодирование 

Знаки первичного алфавита (например, русского) кодируются комбинациями символов двоичного алфавита. Это: 0 и 1. Длина кодов и, соответственно, длительность передачи отдельного кода, могут различаться. Длительности элементарных сигналов при этом одинаковые.

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

Суммарная длительность сообщения будет меньше, если знакам первичного алфавита, которые встречаются в сообщении чаще, присвоить меньше по длине коды, а тем, относительная частота которых меньше – коды более длинные. Другими словами, коды знаков первичного алфавита, вероятность появления которых в сообщении выше, следует строить из возможно меньшего числа элементарных сигналов, а длинные коды использовать для знаков с малыми вероятностями [2,с.68-79].

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

00100010000111010101110000110

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

Первый состоит в использовании  специальной комбинации элементарных сигналов, которая интерпретируется декодером как – разделитель  знаков. Его называют «Неравномерный код с разделителем».

Разделителем отдельных  кодов может быть последовательность 00 (признак конца знака), а разделителем слов – 000 (признак конца слова - пробел). При этом можно установить правила  построения кодов, например некоторые  из таких:

- код признака конца  знака может включен в код  буквы, поскольку не существует  отдельно (т.е кода всех букв  будут заканчиваться 00);

- коды букв не должны  содержать двух и более нулей  подряд в середине (иначе они  будут восприниматься как конец  знака);

- разделителю слов (000) всегда  предшествует признак конца знака  и др.

Неравномерный код может быть однозначно декодирован, если никакой из кодов не совпадает с началом (префиксом) какого – либо иного более длинного кода.

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

ал м р у ы

10 010 00 11 0110 0111

В качестве примера рассмотрим таблицу префиксных кодов:

Пусть требуется декодировать сообщение: 0010001000011101010111000110, в котором  отсутствуют коды конца знака  и слова.

Декодирование производится следующим образом:

1. Выписывается первый слева символ. Это 0. Сравнивается с таблицей

кодов. Совпадений нет. Выписывается второй символ. Это 0. Получили слова 00. Ему соответствует буква «м».

2. Выписывается третий слева символ. Это 1. Сравнивается с таблицей

Кодов. Совпадений нет. Выписывается четвертый символ. Это 0. Получили слова 10. Ему соответствует буква «а».

Процесс циклический и  повторяется до тех пор, пока не расшифруется все слова. В примере зашифровано  текст «Мама мыла раму»

00 10 00 10 - мама

00 0111 010 10  - мыла

11 10 00 0110  - раму

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

Равномерное алфавитное двоичное кодирование. Байтовый код.

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

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