Первичные стандартные коды
Кодирование – это отображение некоторого набора знаков в другой набор знаков. Множество образов при таком отображении называется кодом. Пусть, например, мы имеем сообщение «to get out of bed on the wrong side » Это последовательность графем (букв английского алфавита и пропусков между словами) кодирует пословицу «встать с левой ноги» на английском языке. Всего использовано 35 графем. При письменной передаче, сканировании и распознавании текста легко могут произойти ошибки, например, из-за похожести некоторых букв. Чтобы уменьшить количество ошибок при передаче, сообщение кодируют. Обычно используют двоичный код с цифрами {0, 1}. Для букв латиницы и некоторых знаков вполне достаточно пятиразрядного кода от 00000 до 11111. Всего 25 = 32 двоичных последовательностей для 32-х символов.
| Упражнение 1. Сообщение «to get out of bed on the wrong side » закодировали пятиразрядным двоичным кодом. Сколько потребовалось двоичных знаков? 35*5 = 175 |
Сообщение «to get out of bed on the wrong side » можно рассматривать как набор слов-знаков над набором всех слов английского языка. Англо-русский словарь средних возможностей содержит примерно 70000 слов и выражений. Ставим в соответствие каждому слову, словоформе число и кодируем сообщение такими числами. Алфавит большой, зато чисел в передаче будет всего 9. Правда, возникает проблема поиска соответствий при кодировании и декодировании.
И, в конце концов, можно рассматривать всё предложение как символ-знак над множеством всех предложений английского языка. Это естественно, так как на русский язык эта пословица переводится как «встать с левой ноги» - тоже символ. Достоинство очевидно: всё сообщение кодируется одним числом. Но возможных предложений в естественном языке бесконечно много. Поэтому практически такой многообещающий подход можно применять только в частных случаях при строгом ограничении используемых предложений.
Вывод. Увеличивая размер алфавита, уменьшаем длину сообщения. Уменьшая размер алфавита, увеличиваем длину сообщения. То есть, выигрывая в расходах на передачу, проигрываем в «цене» кодирования/декодирования, и наоборот.
й международный телеграфный код
Жан Мори́с Эми́ль Бодо́
(фр. Jean-Maurice-Émile Baudot)
|
В 1874 французский инженер Ж.Бодо году предложил для телеграфной связи использовать двоичный равномерный пятиэлементный код. Учитывая заслуги Бодо в области телеграфии, Международный консультативный комитет по телефонии и телеграфии (МККТТ) в 1927 году постановил единицу скорости манипуляции называть в его честь Бодом. Если в секунду передается один элементарный импульс, то скорость передачи равна 1 Бод. |
Поскольку пятиэлементный двоичный код позволяет получить только 32 кодовые комбинации (25 = 32), а число необходимых кодовых комбинаций для передачи различных букв, цифр и знаков равно 56, то при использовании кода Бодо применяется двухрегистровый режим работы. При этом весь первичный алфавит (буквы, цифры, знаки) разделяется на две равные группы (два регистра), в каждой оказывается по 28 символов алфавита. Каждому регистру приписывается специально выделяемая кодовая комбинация, которая является его признаком (адресом). При переходе от одного регистра к другому производится смена адреса, и те же самые кодовые комбинации используются теперь для передачи величин, входящих в состав второго регистра.
В тех случаях, когда структура передаваемых сообщений такова, что переходы с одного регистра на другой и обратно используются сравнительно редко, среднее время, требуемое для передачи одного знака сообщения при пятиэлементных кодовых комбинациях, оказывается меньшим по сравнению с использованием непосредственно шестиэлементного кода (26 = 64).
Для телеграфных аппаратов с русско-латинским алфавитом был разработан вариант Международного телеграфного кода N2 (МТК-2). Таблица этого равномерного 5-элементного кода составлена так, чтобы на регистрах "буквы латинские" и "цифры" она совпадала с международным стандартом МККТТ. Для русского алфавита введён третий регистр, переход на который осуществляется передачей комбинации из пяти нулей. Разместить 31 русскую букву аналогично латинским не удается, поэтому 5 русских букв помещены в цифровом регистре. Отметим, что знаки в таблице кода размещены таким образом, чтобы соответствующие им кодовые комбинации МТК-2 шли в порядке возрастания номеров этих знаков. Код МТК-2 получил повсеместное распространение и до сих пор широко используется в буквопечатающих телеграфных аппаратах.
Телеграфный трёхрегистровый код МТК-2 был принят в СССР в 1963 году. Код 5-битовый (всего 32 разных комбинации), поэтому используются 3 разных регистра (русский, латинский, цифры), переключаемые управляющими символами РУС, ЛАТ, ЦИФ. Букв Ъ и Ё нет; вместо буквы Ч использовали цифру 4.
| Шестнадцатеричный код | Десятичный код | Двоичный код | Латинские буквы | Русские буквы | Цифры |
| 0x03 | A | А | - | ||
| 0x19 | B | Б | ? | ||
| 0x0E | C | Ц | : | ||
| 0x09 | D | Д | Кто там? | ||
| 0x01 | E | Е | З | ||
| 0x0D | F | Ф | Э | ||
| 0x1A | G | Г | Ш | ||
| 0x14 | H | Х | Щ | ||
| 0x06 | I | И | |||
| 0x0B | J | Й | Ю | ||
| 0x0F | K | К | ( | ||
| 0x12 | L | Л | ) | ||
| 0x1C | M | М | . | ||
| 0x0C | N | Н | , | ||
| 0x18 | O | О | |||
| 0x16 | P | П | |||
| 0x17 | Q | Я | |||
| 0x0A | R | Р | |||
| 0x05 | S | С | ' | ||
| 0x10 | T | Т | |||
| 0x07 | U | У | |||
| 0x1E | V | Ж | = | ||
| 0x13 | W | В | |||
| 0x1D | X | Ь | / | ||
| 0x15 | Y | Ы | |||
| 0x11 | Z | З | + | ||
| 0x08 | Возврат каретки | ||||
| 0x02 | Перевод строки | ||||
| 0x1F | Буквы латинские | ||||
| 0x1B | Цифры | ||||
| 0x04 | Пробел | ||||
| 0x00 | Буквы русские |
МТК-2 основан на международном телеграфном коде № 2 (ITA2), рекомендованном Международным консультативным комитетом по телефонии и телеграфии в 1932 году (в международном коде 00000 не используется).
Соответствие между английским и русским регистрами, принятое в МТК-2, было использовано при создании компьютерных кодировок КОИ-7 и КОИ-8.
Кодирование сообщения «to get out of bed on the wrong side » увеличит число знаков. Исходное сообщение состоит из 35 символов, кодированное – из 35 * 5 = 175 символов. Зато технически гораздо проще осуществить передачу и приём сообщения и меньше возможностей для ошибки. Декодировать несложно, поскольку каждый символ исходного алфавита кодируется ровно пятью двоичными знаками. Надо только не сбиться со счёта.
| Упражнение 2. 1. На приемник поступила последовательность 11111101000000100100000001100001100001001101101010, о которой известно, что она закодирована трёхрегистровым кодом МТК-2. Декодируйте ее. HE ОН 4 2. Закодируйте свое имя, представленное латинскими буквами. 3. Как следует отсортировать таблицу, чтобы было удобно закодировать текст «to get out of bed on the wrong side »? А для декодирования? 4.Предложите структуру данных для программной реализации кодирования и декодирования текста, состоящего из латинских букв. Реализуйте такую программу. |
В вычислительной технике широко используется ASCII – семиразрядный код, позволяющий использовать 128 кодировочных слов, а также его восьмиразрядное расширение из 256 кодировочных слов. Чем больше разрядность кода, тем больше символов можно закодировать с его помощью. 16-разрядный Unicode позволяет закодировать 216 = 65536 символов. Этого достаточно даже для кодирования китайских иероглифов. Существуют и 32-х разрядные кодировки.
Код Морзе
Сэ́мюэл Фи́нли Бриз Мо́рзе (Samuel Finley Breese Morse)
|
Наибольшую известность и распространение получил код, предназначенный для передачи телеграфных сообщений, предложенный в 1837 году американским изобретателем С.Морзе. Код Морзе, достаточно широко применяемый и до настоящего времени, является неравномерным, т.е. его комбинации содержат различное число знаков.
|
Используется набор знаков азбуки Морзе {∙, ‑}. В нём каждая буква кодируется набором точек и тире, причем наиболее часто встречающиеся буквы кодируются более короткой последовательностью. Для передачи русских букв используются коды сходных латинских букв.
Например, Т ‑, Е ∙, Щ ‑ ‑ ∙ ‑, А ∙ ‑. Последовательность знаков ‑ ∙ ‑ ‑ ∙ ‑ ∙ ‑ декодировать проблематично, так как буквы нельзя отделить одну от другой по их длине.
Конечные двоичные коды можно описывать также с помощью кодового дерева. На рисунке ниже изображено кодовое дерево для русской азбуки Морзе.
| Упражнение 3. 1. Закодируйте свое имя кодом Морзе. 2.Постройте кодовое дерево для английской азбуки Морзе. |
К положительным свойствам кода Морзе следует отнести высокую помехоустойчивость и возможность приёма на слух. Высокая помехоустойчивость кода Морзе обусловлена его большой избыточностью. При приёме на слух (за счёт модуляции посылок тональной частотой) высокая достоверность принимаемой информации объясняется тем, что процесс преобразования сигнала в знак осуществляется человеком, который при достаточном опыте может различать сигналы, значительно искажённые помехами.
Условие Фано
Двоичные коды с постоянной длиной кодового слова в технике встречаются гораздо чаще, чем коды с переменной длиной. Для кодов с постоянной длиной кодового слова декодирование выполняется просто, надо только аккуратно вести отсчет. Для кодов с переменной длиной кодовых слов расположение стыков, вообще говоря, восстановить нельзя. Сообщение может не декодироваться совсем, или декодироваться неоднозначно. Чтобы этого не случилось, коды с переменной длиной должны удовлетворять условию Фано:
| Никакое кодовое слово не является началом другого слова („свойство префиксности"). |
Фактически код Морзе ‑ это троичный код, так как в нём используется знак «пропуск», отделяющий букву от буквы. Общепринятое правило радистов гласит «продолжительность точки равна продолжительности паузы, продолжительность тире равна трём продолжительностям точки, продолжительность пропуска равна трём продолжительностям паузы». Установим соответствие
∙ 01
‑ 0111
«пропуск» 000
Здесь 0 – это продолжительность паузы (нет звука), 1 – продолжительность точки (есть звук).
| Упражнение 4.Декодируйте последовательность 01110000100001110111010111000010111000. |
Для кодов переменной длины, удовлетворяющим условию Фано, стык между кодовыми словами определяется тем моментом, когда „дальше не читается". Условие Фано является достаточным, но не необходимым условием однозначной декодируемости. Другими словами, можно придумать код не удовлетворяющий условию Фано, но позволяющий однозначное декодирование. Например, пусть A = 1, а B = 101. Очевидно, что слова 1011101 110111 и другие декодируются однозначно.
Тривиальная возможность обеспечить выполнение условия Фано состоит в том, чтобы каждое кодовое слово начинать специальным знаком (или группой знаков), называемы разделителем. Это, очевидно, имеет место в случае кода Морзе, а именно пауза является разделителем для последовательности точек - тире, а группа знаков 000 (пропуск) — разделителем при двоичном кодировании кода Морзе. С технической точки зрения при передаче по телеграфу также передается разделитель (синхронизирующий «такт разбивки»).
| Упражнение 5. По каналу связи передаются сообщения, каждое из которых содержит 16 букв А, 8 букв Б, 4 буквы В и 4 буквы Г (других букв в сообщениях нет). Каждую букву кодируют двоичной последовательностью. При выборе кода учитывались два требования: а) ни одно кодовое слово не является началом другого (это нужно, чтобы код допускал однозначное декодирование); б) общая длина закодированного сообщения должна быть как можно меньше. Какой код из приведённых ниже следует выбрать для кодирования букв А, Б, В и Г? 1) А:0, Б:10, В:110, Г:111 2) А:0, Б:10, В:01, Г:11 3) А:1, Б:01, В:011, Г:001 4) А:00, Б:01, В:10, Г:11 Ответ обоснуйте. 1 Упражнение 6. По каналу связи передаются сообщения, содержащие только 5 букв А, И, К, О, Т. Для кодирования букв используется неравномерный двоичный код с такими кодовыми словами: А — 0, И — 00, К — 10, О — 110, Т — 111. Удовлетворяет ли данный код условию Фано? Среди приведённых ниже слов укажите то, код которого можно декодировать только одним способом. 1) КАА 2) ИКОТА 3) КОТ 4) ни одно из сообщений не подходит Упражнение 7. По каналу связи передаются сообщения, содержащие только 4 буквы П, О, С, Т; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, П используются такие кодовые слова: Т: 111, О: 0, П: 100. Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением. Указание. Для решения этой задачи используйте кодовое дерево. 101 |
При параллельной передаче мы, в отличие от последовательной передачи, ограничены кодами со словами постоянной длины. Для n-разрядного двоичного кода используется n параллельных двоичных каналов передачи. В случае оптического, электростатического, электролитического и электромагнитного телеграфа путь технического прогресса шёл от параллельной к последовательной передаче.
Вопрос о том, какие коды являются оптимальными с точки зрения передачи, изучается в теории информации.