Кодирование информации — различия между версиями
Nechaev (обсуждение | вклад) |
Nechaev (обсуждение | вклад) |
||
| Строка 6: | Строка 6: | ||
В более узком смысле кодированием информации называют представление информации в виде кода. | В более узком смысле кодированием информации называют представление информации в виде кода. | ||
Средством кодирования служит таблица соответствия знаковых систем, которая устанавливает взаимно однозначное соответствие между знаками или группами знаков двух различных знаковых систем. | Средством кодирования служит таблица соответствия знаковых систем, которая устанавливает взаимно однозначное соответствие между знаками или группами знаков двух различных знаковых систем. | ||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
== Код == | == Код == | ||
| Строка 21: | Строка 12: | ||
|definition='''Код''' — правило (алгоритм) сопоставления каждому конкретному сообщению строго определённой комбинации символов (знаков или сигналов). Кодом также называется отдельная комбинация таких символов (знаков) — слово. Для различия этих терминов, код в последнем значении ещё называется ''кодовым словом''. | |definition='''Код''' — правило (алгоритм) сопоставления каждому конкретному сообщению строго определённой комбинации символов (знаков или сигналов). Кодом также называется отдельная комбинация таких символов (знаков) — слово. Для различия этих терминов, код в последнем значении ещё называется ''кодовым словом''. | ||
}} | }} | ||
| + | Пусть U {{---}} множество исходных символов, Z {{---}} кодовый алфавит, Z* {{---}} строчки из Z. | ||
| + | Код {{---}} отображение c : U <tex>\rightarrow</tex> Z*. c* : U* <tex>\rightarrow</tex> Z*. c*(x1x2..xn) = c(x1)c(x2)..c(xn) | ||
| + | |||
==== Виды кодов ==== | ==== Виды кодов ==== | ||
| − | * | + | * '''Код фиксированной длины''' (fixed-length code) {{---}} кодирование каждого символа производится с помощью строк одинаковой длины. Также он называется ''равномерным'' или ''блоковым'' кодом. |
* '''Код переменной длины''' (variable-length code) {{---}} кодирование производится с помощью строк переменной длины. Также называется ''неравномерным кодом''. | * '''Код переменной длины''' (variable-length code) {{---}} кодирование производится с помощью строк переменной длины. Также называется ''неравномерным кодом''. | ||
* '''Разделимый код''' {{---}} код, в котором любое слово, составленное из элементарных кодов, единственным образом разлагается на элементарные коды. | * '''Разделимый код''' {{---}} код, в котором любое слово, составленное из элементарных кодов, единственным образом разлагается на элементарные коды. | ||
| Строка 40: | Строка 34: | ||
Предпочтение префиксным кодам отдается из-за того, что они упрощают декодирование. Поскольку никакое кодовое слово не выступает в роли префикса другого, кодовое слово, с которого начинается закодированный файл, определяется однозначно. Начальное кодовое слово, с которого начинается закодированный файл, определяется однозначно. Начальное кодовое слово легко идентифицировать, преобразовать его в исходный символ и продолжить декодирование оставшейся части закодированного файла. | Предпочтение префиксным кодам отдается из-за того, что они упрощают декодирование. Поскольку никакое кодовое слово не выступает в роли префикса другого, кодовое слово, с которого начинается закодированный файл, определяется однозначно. Начальное кодовое слово, с которого начинается закодированный файл, определяется однозначно. Начальное кодовое слово легко идентифицировать, преобразовать его в исходный символ и продолжить декодирование оставшейся части закодированного файла. | ||
| − | |||
| − | |||
| − | |||
Пример: | Пример: | ||
| − | + | U = {a,b,c}; Z = {0,1}; | |
| + | c(a) = 00; c(b) = 01; c(c) = 1; | ||
| + | Закодируем строку: abacaba | ||
c*(abacaba) = 0001001000100 | c*(abacaba) = 0001001000100 | ||
Такой код можно однозначно разбить на слова: | Такой код можно однозначно разбить на слова: | ||
00 01 00 1 00 01 00 | 00 01 00 1 00 01 00 | ||
поэтому он является префиксным. | поэтому он является префиксным. | ||
| − | Предположим, что последовательность передалась неверно и стала: | + | |
| + | ==== Недостатки префиксных кодов ==== | ||
| + | * Так как префиксные коды являются кодами переменной длины, а данные, в основном, считываются блочно, код приходится считывать побитово, что значительно значительно замедляет скорость считывания данных | ||
| + | * При появлении ошибок в кодовой комбинации, при определенных обстоятельствах, может привести к неправильному декодированию не только данной, но и последующей кодовой комбинации, в отличии от равномерных кодов, где ошибка в кодовой комбинации приводит к неправильному декодированию только ее. | ||
| + | |||
| + | Предположим, что предыдущая последовательность передалась неверно и стала: | ||
0001001'''1'''00100 | 0001001'''1'''00100 | ||
Разобьем ее согласно словарю: | Разобьем ее согласно словарю: | ||
Версия 03:13, 27 ноября 2011
| Определение: |
| Кодирование информации — процесс преобразования информации из одной формы в другую. |
Обычно в процессе кодирования информация преобразуется из формы, удобной для непосредственного использования, в форму, удобную для передачи, хранения или автоматической обработки. В более узком смысле кодированием информации называют представление информации в виде кода. Средством кодирования служит таблица соответствия знаковых систем, которая устанавливает взаимно однозначное соответствие между знаками или группами знаков двух различных знаковых систем.
Содержание
Код
| Определение: |
| Код — правило (алгоритм) сопоставления каждому конкретному сообщению строго определённой комбинации символов (знаков или сигналов). Кодом также называется отдельная комбинация таких символов (знаков) — слово. Для различия этих терминов, код в последнем значении ещё называется кодовым словом. |
Пусть U — множество исходных символов, Z — кодовый алфавит, Z* — строчки из Z. Код — отображение c : U Z*. c* : U* Z*. c*(x1x2..xn) = c(x1)c(x2)..c(xn)
Виды кодов
- Код фиксированной длины (fixed-length code) — кодирование каждого символа производится с помощью строк одинаковой длины. Также он называется равномерным или блоковым кодом.
- Код переменной длины (variable-length code) — кодирование производится с помощью строк переменной длины. Также называется неравномерным кодом.
- Разделимый код — код, в котором любое слово, составленное из элементарных кодов, единственным образом разлагается на элементарные коды.
Примеры кодов
- Азбука Морзе
- ASCII
Префиксный код
| Определение: |
| Префиксный код — код, в котором никакое кодовое слово не является префиксом какого-то другого кодового слова. |
Любой префиксный код является однозначно декодируемым и разделимым. Также префиксный код иногда называют мнгновенным кодом. Оптимальное сжатие данных, которого можно достичь с помощью кодов, всегда достижимо при использовании префиксного кода.
Предпочтение префиксным кодам отдается из-за того, что они упрощают декодирование. Поскольку никакое кодовое слово не выступает в роли префикса другого, кодовое слово, с которого начинается закодированный файл, определяется однозначно. Начальное кодовое слово, с которого начинается закодированный файл, определяется однозначно. Начальное кодовое слово легко идентифицировать, преобразовать его в исходный символ и продолжить декодирование оставшейся части закодированного файла.
Пример:
U = {a,b,c}; Z = {0,1};
c(a) = 00; c(b) = 01; c(c) = 1;
Закодируем строку: abacaba
c*(abacaba) = 0001001000100
Такой код можно однозначно разбить на слова:
00 01 00 1 00 01 00
поэтому он является префиксным.
Недостатки префиксных кодов
- Так как префиксные коды являются кодами переменной длины, а данные, в основном, считываются блочно, код приходится считывать побитово, что значительно значительно замедляет скорость считывания данных
- При появлении ошибок в кодовой комбинации, при определенных обстоятельствах, может привести к неправильному декодированию не только данной, но и последующей кодовой комбинации, в отличии от равномерных кодов, где ошибка в кодовой комбинации приводит к неправильному декодированию только ее.
Предположим, что предыдущая последовательность передалась неверно и стала: 0001001100100 Разобьем ее согласно словарю: 00 01 00 1 1 00 1 00 a b a c c a c a
Полученная строка совпадает только в битах, которые находились до ошибочного, поэтому декодирование неравномерного кода, содержащего ошибки, может дать абсолютно неверные результаты.
- Необходимость хранить словарь декодировки символов.
Примеры префиксных кодов
- Код Хаффмана
- Код Шеннона-Фано
- UTF-8 — префиксный, так как является блоковым.
См. также
Литература
- Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. Алгоритмы. Построение и анализ — Издательство: «Вильямс», 2011 г. - 1296 стр. — ISBN 978-5-8459-0857-5, 5-8459-0857-4, 0-07-013151-1
- Джеймс Андерсон. Дискретная математика и комбинаторика — Издательство: «Вильямс», 2004 г. - 960 стр. — ISBN 978-0-13-086998-2
- Ф. А. Новиков. Дискретная математика для программистов — Издательство: «Питер», 2001 г. - 304 стр. — ISBN 5-94723-741-5 978-5-94723-741-2
