"Информатика (базовый и углублённый уровни) (в 2 частях)", Поляков К.Ю., Еремин Е.А.
Кодирование заменяет исходные данные их представлением по установленному правилу. Так компьютер хранит и передаёт тексты, числа, изображения и звук в виде последовательностей битов. Чтобы восстановить данные, получатель должен знать правило и пользоваться той же таблицей кодов, что и отправитель. Важные свойства кода — длина его слов и возможность однозначно разделить их при чтении.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Кодирование — замена исходных данных их представлением по установленному правилу. Если правило известно, можно выполнить обратное преобразование — декодирование. Это позволяет хранить и передавать информацию в форме, удобной для устройства или канала связи.
Алфавит кодирования — набор символов, из которых составляют кодовые комбинации. Например, двоичный алфавит содержит только 0 и 1. Такой алфавит удобен компьютеру: электронная схема может различать два состояния сигнала.
Кодовое слово — последовательность символов алфавита кодирования, которую сопоставляют исходному символу или целому сообщению. Например, букве можно поставить в соответствие 101. Понятие нужно, чтобы обсуждать, как именно записывается каждый элемент исходных данных.
Равномерный код — код, в котором все кодовые слова имеют одинаковую длину. В неравномерном коде длины слов различаются. Фиксированная длина упрощает разделение и обработку слов, а переменная может сократить запись, если короткие слова чаще назначают частым символам.
При кодировании каждому исходному символу или сообщению ставят в соответствие кодовое слово. Получатель должен знать это соответствие и правила чтения, иначе он не сможет установить, какой исходный элемент обозначают полученные знаки. Поэтому одного факта, что данные записаны битами, недостаточно для восстановления исходного текста.
Компьютер оперирует электрическими сигналами, которые удобно распознавать как одно из двух состояний. Их условно обозначают 0 и 1, получая двоичный алфавит. Комбинациями этих знаков можно записать числа, а по согласованным правилам — символы текста, цвета пикселей и значения звукового сигнала.
У двоичного слова длины k на каждой позиции есть два возможных значения. Поэтому всего существует 2ᵏ разных слов: например, при k = 2 получаются 00, 01, 10 и 11. Для N исходных символов выбирают наименьшее целое k, при котором 2ᵏ ≥ N; округление вверх необходимо, потому что длина слова не может быть дробной.
Равномерный код удобно читать и обрабатывать: зная длину слова, поток можно разделить на одинаковые группы. Неравномерный код помогает экономить место, если часто встречающимся символам назначить короткие слова, а редким — длинные. Но границы слов должны быть понятны: если не проверить правило разделения, одному потоку могут соответствовать разные сообщения.
Таблица кодов связывает каждый символ с числом или двоичной последовательностью. Например, таблица кодировки текста сообщает, какие числовые значения соответствуют буквам и знакам. Если отправитель и получатель используют разные таблицы, один набор битов может обозначать разные символы, поэтому для чтения требуется согласованная кодировка.
| Свойство | Равномерный код | Неравномерный код |
|---|---|---|
| Длина кодовых слов | Одинаковая для всех слов | Может различаться |
| Как определить границы кодовых слов | Разбить поток на группы заданной длины | Использовать правило декодирования или разделители |
| Однозначность декодирования | Обеспечивается известной длиной и таблицей соответствий | Требует проверки: возможны неоднозначные разбиения |
| Преимущества | Простые чтение и обработка | Можно сократить среднюю длину сообщения |
| Ограничения и условия применения | Часто использует лишние биты для частых символов | Нужно однозначно находить границы слов |
Сравнивайте коды по строкам: сначала выясните, как делится поток, затем оцените однозначность и удобство. Если важна экономия, учитывайте не только длины слов, но и частоты символов. Короткий код не будет удобен, если сообщение нельзя восстановить единственным способом.
Задача 1. Для пяти символов требуется равномерный двоичный код минимальной длины. Нужно определить, сколько разрядов выделить каждому символу, и проверить, хватит ли комбинаций.
Ответ: минимальная длина равна 3 битам; из восьми комбинаций можно выбрать пять.
Задача 2. Используются кодовые слова 0, 10 и 11. Нужно декодировать последовательность 10110. Проверим, что ни одно из заданных слов не является началом другого: слово 0 начинается с 0, а слова 10 и 11 различаются вторым битом.
Ответ: последовательность декодируется однозначно и соответствует словам 10, 11, 0.
Задача 3. Символы A, B, C встречаются соответственно 5, 3 и 2 раза. Сравним равномерный код A = 00, B = 01, C = 10 и неравномерный код A = 0, B = 10, C = 11. У неравномерного набора ни одно слово не является началом другого, значит, его можно декодировать слева направо без разделителей.
Ответ: второй код экономнее для заданных частот и однозначно декодируется без разделителей.
Ошибка — считать, что для N символов достаточно длины log₂N без округления. Такое значение может быть дробным, а длина слова должна быть целым числом; проверяйте условие 2ᵏ ≥ N и выбирайте наименьшее целое k. Например, для пяти символов двух разрядов не хватает, потому что 2² = 4.
Не путайте символ исходного алфавита с символом двоичного алфавита. Буква — исходный символ, а её кодовое слово может состоять из нескольких нулей и единиц. Проверяйте, что в примере вы называете отдельной буквой, а что — последовательностью битов, которой она закодирована.
При декодировании неравномерного кода нельзя произвольно делить поток на части. Если одно кодовое слово может начинать другое, разбиение иногда становится неоднозначным. Перед чтением проверьте правила разделения и попробуйте последовательно разобрать поток разными способами.
Ещё одна ошибка — считать, что биты сами по себе однозначно задают текст. Для восстановления нужны правило кодирования и согласованная таблица символов; разные таблицы могут по-разному трактовать одну последовательность. Проверьте, известна ли используемая кодировка и совпадает ли она у отправителя и получателя.
Чтобы понимать двоичные коды, полезно знать двоичную запись чисел и представлять, что данные можно записать последовательностью битов. Кодирование применяют при хранении и передаче текстов, изображений и звука, а также при сжатии данных. Понимание кодовых слов и однозначного декодирования пригодится при изучении алгоритмов сжатия и передачи информации.
Почему компьютер использует именно нули и единицы?
Электронным устройствам удобно различать два устойчивых состояния, например наличие и отсутствие сигнала. Их обозначают цифрами 1 и 0, поэтому данные представляют последовательностями этих цифр.
Как найти минимальную длину двоичного кода для заданного числа символов?
Нужно найти наименьшее целое k, для которого 2ᵏ не меньше числа символов N. Именно столько разных двоичных слов длины k существует.
Чем равномерный код отличается от неравномерного?
В равномерном коде все слова имеют одинаковую длину, а в неравномерном длины различаются. Неравномерный код может уменьшить среднюю длину сообщения, но его слова должны позволять однозначно восстановить границы.
Почему последовательность битов иногда нельзя однозначно декодировать?
Если неизвестно правило разделения слов, одни и те же биты можно разбить на кодовые слова несколькими способами. Например, кодовые слова 0, 01 и 1 допускают для последовательности 01 разбор и как одно слово, и как два.
Зачем при чтении текста нужна таблица кодировки?
Таблица связывает символы с числовыми или двоичными кодами. Разные таблицы могут назначать одной и той же последовательности битов разные символы, поэтому для чтения текста нужно знать используемую кодировку.
§ 6. Кодирование
