Схемы кодирования с переменной длиной

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

Пионер телеграфной передачи данных Сэмюэл Морзе разработал код, в ко- тором каждая буква соответствовала серии точек (короткие импульсы) и тире (длинные импульсы). В нашем контексте точки и тире можно заменить нулями и единицами, так что задача сводится к простому отображению символов на цепоч- ки битов, как и в кодировке ASCII. Морзе понимал, что эффективность передачи данных можно повысить за счет кодирования более частых символов короткими строками, и выбрал именно такое решение. (За информацией об относительных частотах букв английского языка он обратился к местным типографиям.) В коде Морзе букве «e» соответствует 0 (точка), букве «t» — 1 (тире), букве «a» — 01 (точ- ка-тире), и вообще более частым буквам соответствуют более короткие цепочки.

В коде Морзе для представления букв используются настолько короткие цепоч- ки, что кодирование слов становится неоднозначным. Например, из того, что мы знаем о кодировке букв «e», «t» и «a», становится видно, что цепочка 0101 может соответствовать любой из последовательностей «eta», «aa», «etet» или «aet». (Также существуют другие возможные варианты с другими буквами.) Для разрешения этой неоднозначности при передаче кода Морзе буквы разделяются короткими паузами (так что текст «aa» будет кодироваться последовательностью точка-тире- пауза-точка-тире-пауза). Это решение — очень короткие битовые цепочки с пау- зами — выглядит разумно, но оно означает, что буквы кодируются не 0 и 1; фак- тически применяется алфавит из трех букв — 0, 1 и «пауза». Следовательно, если потребуется что-то закодировать только битами 0 и 1, потребуется дополнительное кодирование, которое ставит в соответствие паузе последовательность битов.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Схемы кодирования с переменной длиной:

  1. СХЕМЫ ВОЗДЕЙСТВИЯ ПРИ КОДИРОВАНИИ ЧЕЛОВЕКА
  2. 2.6. Правила кодирования
  3. 4.14. СХЕМЫ ЖАНА ПИАЖЕ
  4. Положительное кодирование.
  5. ПРИНЦИП КОДИРОВАНИЯ СПЕЦИФИЧЕСКОГО
  6. СУТОЧНАЯ И СЕЗОННАЯ АКТИВНОСТЬ ОРГАНОВ (ЭЛЕМЕНТОВ СХЕМЫ У СИН)
  7. ПЕРЕМЕННАЯ ПРОМЕЖУТОЧНАЯ
  8. ПЕРЕМЕННАЯ
  9. ПЕРЕМЕННАЯ ЗАВИСИМАЯ
  10. ПЕРЕМЕННАЯ НЕЗАВИСИМАЯ
  11. ПЕРЕМЕННАЯ КОНТРОЛИРУЕМАЯ
  12. Пять переменных У. Мичела.
  13. Сопротивление переменам в нас
  14. Теория «типовых переменных» и индивидуального выбора (Т. Парсонс).
  15. Ситуация действия и «Pattern Variables» («типовые переменные»)
  16. Сознание — первый шаг к выздоровлению и переменам
  17. Самоодобрение и самопринятие - ключ к положительным переменам в нашей жизни
  18. Правило разработки графических схем
  19. Правило разработки графических схем