Теория кодирования. Виды кодирования

Теория кодирования. Виды кодирования Основные понятия теории кодирования Ранее средства кодирования играли вспомогательную роль и не рассматривались как  отдельный предмет математического изучения, но с появлением компьютеров ситуация  радикально изменилась. Кодирование буквально пронизывает информационные технологии и является центральным вопросом при решении самых разных (практически всех) задач  программирования: ۞ представление данных произвольной природы (например, чисел, текста, графики) в   памяти компьютера; ۞ защита информации от несанкционированного доступа; ۞ обеспечение помехоустойчивости при передаче данных по каналам связи; ۞ сжатие информации в базах данных.   Теория кодирования ­ это раздел теории информации, изучающий способы  отождествление сообщений с отображающими  их сигналами. Задача: Согласовать источник информации с каналом связи. Объект: Дискретная или непрерывная информация, поступающая к потребителю через  источник информации.  Кодирование – это преобразования информации в формулу удобную для передачи по  определенному каналу связи. Примером кодирования в математике является метод координат, введенный Декартом,  который дает возможность изучать геометрические объекты через их аналитическое  выражение в виде чисел, букв и их комбинаций — формул. Понятие кодирование означает преобразование информации в форму, удобную для  передачи по определенному каналу связи. Декодирование – восстановление принятого сообщения из­за кодированного вида в вид  доступный для потребителя. Тема 5.2.  Алфавитное кодирование В общем случае задачу кодирования можно представить следующим образом. Пусть заданы два алфавита А и В, состоящие из конечного числа символов:   и   .  Элементы алфавита называются буквами. Упорядоченный набор в  алфавите А назовем словом   ,где  обозначается п =l( )=| |. , число п показывает количество букв в слове и называется длиной слова  ,   Пустое слово обозначается: Для слова   буква a1, называется началом, или префиксом, слова  буква an — окончанием, или постфиксом, слова  . , а      Слова можно соединять. Для этого префикс второго слова должен следовать сразу за  постфиксом первого, при этом в новом слове они, естественно, утрачивают свой статус,  если только одно из слов не было пустым.     Соединение слов   и   обозначается  , соединение п одинаковых слов    обозначается  , причем  .     Множество всех непустых слов алфавита А обозначим А*:       Множество А называют алфавитом сообщений, а множество В — кодирующим  алфавитом. Множество слов, составленных в алфавите В, обозначим В*. Обозначим через F отображение слов алфавита А в алфавит В. Тогда слово    назовем кодом слова  .       Кодированием называют универсальный способ отображения информации при ее  хранении, передаче и обработке в виде системы соответствий между элементами  сообщений и сигналами, при помощи которых эти элементы можно зафиксировать. Таким  образом, код — правило однозначного преобразования (т.е. функция) сообщения из одной  символической формы представления (исходного алфавита А) в другую (объектный  алфавит В), обычно без каких­либо потерь информации. Процесс преобразования F:  А* В*→  слов исходного алфавита А в алфавит В называется кодированием информации.     Процесс обратного преобразования слова  называется декодированием. Таким образом, декодирование — функция, обратная F,  т.е. F­1.  в слово        Так как для любого кодирования должна выполняться операция декодирования, то  отображение должно быть обратимым (биекция).     Если |B|= m, то F называется m­ичным кодированием, наиболее распространенный  случай В = {0, 1}­ двоичное кодирование. Именно этот случай и рассматривается в  дальнейшем.     Если все кодовые слова имеют одинаковую длину, то код на­ зывается равномерным, или блочным.     Алфавитное (или побуквенное), кодирование можно задать таблицей кодов. Кодом или кодирующей функцией, будет служить некоторая подстановка  . Тогда   , где  ,   .       Такое побуквенное кодирование обозначается  называется множеством элементарных кодов. Алфавитное кодирование можно  использовать для любого множества сообщений. Таким образом, алфавитное кодирование  является самым простым, и его всегда можно ввести на непустых алфавитах. . Множество кодов букв ПРИМЕР Пусть заданы алфавиты  А = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}  В = {0, 1}. Тогда таблица кодирования может быть подстановкой:   .     Это двоично­десятичное кодирование, оно является взаимнооднозначным и потому  допускает декодирование. Однако схема    не является взаимно­однозначной. Например, набор из шести единиц 111111 может  соответствовать как слову 333, так и 77,  а также 111111, 137, 3311 или 7111 плюс любая  перестановка.     Схема алфавитного кодирования  называется   префиксной, если элементарный код  одной буквы не является префиксом элементарного кода другой буквы.     Схема алфавитного кодирования  называется разделимой, если любое слово, составлен­ ное из элементарных кодов, разлагается на элементарные коды единственным образом.     Алфавитное кодирование с разделимой схемой допускает декодирование. Можно  доказать, что префиксная схема является разделимой.     Для того чтобы схема алфавитного кодирования была разделимой, необходимо, чтобы  длины элементарных кодов удовлетворяли соотношению, известному какнеравенство  Макмиллана. Неравенство Макмиллана Если схема алфавитного кодирования разделима, то справедливо неравенство     ПРИМЕР      Схема алфавитного кодирования  А={ а, b} и В={0, 1},  является разделимой, т. к. ,  , и, значит, выполняется неравенство Макмиллана     Данная схема префиксной не является, т.к. элементарный код буквы  а   является  префиксом элементарного кода буквы b. Тема 5.3. Кодирование с минимальной избыточностью  На практике важно, чтобы коды сообщений имели по возможности наименьшую длину.  Алфавитное кодирование пригодно для любых сообщений, если же про множество всех  слов алфавита А ничего не известно, то точно сформулировать задачу оптимизации трудно. Однако на практике часто доступна дополнительная информация. Например, для  сообщений, представленных на естественном языке, такой дополнительной информацией  может быть распределение вероятности появления букв в сообщении. Тогда задача  построения оптимального кода приобретает точную математическую формулировку и  строгое решение. Пусть задана некоторая разделимая схема алфавитного кодирования   . Тогда любая схема   , где упорядоченный  набор   есть перестановка  упорядоченного  , также будет разделимой. В таком случае, если длины элементарных  набора  кодов равны, то их перестановка в схеме не влияет на длину закодированного сообщения. В том случае, если длины элементарных кодов различны, то длина кода сообщения напрямую зависит и от того, какие элементарные коды каким буквам поставлены в соответствие, и от того, каков состав букв в сообщении. Если заданы конкретное сообщение и конкретная схема кодирования, то можно подобрать  такую перестановку кодов, при которой длина кода сообщения будет минимальной. Алгоритм назначения элементарных кодов, при котором  длина кода фиксированного  сообщения S будет минимальна при фиксированной схеме  : ۞ отсортировать буквы в порядке убывания количества вхождений; ۞ отсортировать элементарные коды в порядке возрастания длины; ۞ поставить коды в соответствие буквам в установленном порядке. Пусть задан алфавит   и вероятности появления букв в сообщении: , где рi  — вероятность появления буквы ai, причем буквы с нулевой вероятностью  появления в сообщении исключены и буквы упорядочены по убыванию вероятности их  появления  Для разделимой схемы    алфавитного кодирования при распределении вероятностей Р существует так называемая  средняя цена, или длина кодирования, — это математическое ожидание длины  закодированного сообщения, которая обозначается   и определяется как    ПРИМЕР .  Для разделимой  схемы алфавитного кодирования А={а,b}, В={0,1},    при распределении вероятностей   цена кодирования составляет  а при распределении вероятностей    цена кодирования составляет . Тема 5.4. Кодирование методом Хаффмана Этот алгоритм был изобретен в 1952 году Дэвидом Хаффманом.   Тема 5.5. Арифметическое кодирование Как и в алгоритме Хаффмана, все начинается с таблицы элементов и соответствующих  вероятностей. Допустим, входной алфавит состоит всего из трех элементов: a1, a2 и a3, и  при этом P(a1) = 1/2 P(a2) = 1/3 P(a3) = 1/6 Предположим также, что нам надо закодировать последовательность a1, a1, a2, a3 . Разобьем полуинтервал  [0, 1) на три части в соответствии с вероятностями элементов: Элементу a1 будет соответствовать диапазон [0, 1/2); элементу a2 диапазон [1/2, 1/2 + 1/3),  а элементу a3 ­ диапазон [1/2 +1/3 , 1). Первый элемент сжимаемого файла равен а1. Выберем полуинтервал, соответствующий  ему  [0, 1/2 ): Разобьем его таким же образом на три части: Поскольку второй элемент сжимаемой последовательности тоже равен a1,  снова выбираем  самый нижний диапазон (точнее, теперь уже поддиапазон [0, 1/4)): Аналогичным образом, продолжая процесс для оставшихся элементов входного  файла а2 и а3, получаем такой рисунок: Последним полученным диапазоном будет [5/24, 1/4). Теперь ­ внимание! Любое число из  этого диапазона (например, 0,22) однозначно описывает весь входной файл. Зная  вероятности появления элементов, декодер может правильно разбить диапазон [0, 1) на три части и определить, что число 0,22 находится в поддиапазоне [0, 1/2). В свою очередь, это  означает, что первый элемент декодированного файла равен а1. Затем декодер разобьет  диапазон [0, 1/2) на три части и определит, что число 0,22 находится в поддиапазоне [0,  1/4), следовательно, следующий элемент выходного файла — снова а1 и т. д. Поскольку декодер не может точно определить, когда следует закончить работу  (процесс при желании можно продолжать бесконечно), придется либо явно прописать во  входном файле количество элементов, подлежащих декодированию, либо ввести  специальный символ «конец файла», встретив который, распаковщик остановится. Хотя для описания сжимаемого файла годится любое число конечного диапазона (0.22,  0.222, 0.222222222222,...), выбирать надо, разумеется, то, которое содержит меньше цифр,  поскольку каждая лишняя цифра увеличивает размер выходного файла.  КОДИРОВАНИЕ И ДЕКОДИРОВАНИЕ   ­ процесс представления информации в определенной стандартной форме и обратный проц ессвосстановления информации по ее такому представлению. В математич. литературе код ированием наз.отображение произвольного множества Ав множество конечных последоват ельностей (слов) в нек­ромалфавите В, а декодированием ­ обратное     отображение. Пример ами кодирования являются: представлениенатуральных чисел в r­ичной системе счисления,  при к­ром каждому числу N=i ,2, ... ставится в соответствиеслово b1b2 ... bl в алфавите В r={0, 1, ..., r­ 1} такое, что b1 неравно 0 и b1rl­1+...+ bl­1r+bl=N; преобразованиетекстов на русском языке с  помощью телеграфного кода в последовательности, составленные из посылоктока и пауз ра зличной длительности; отображение, применяемое при написании цифр почтового индекса  (см.рис.). В последнем случае каждой десятичной цифре соответствует слово в алфавите В  2={0, 1} длины 9, вкотором символами 1 отмечены номера использованных линий (напр., ци фре 5 соответствует слово110010011). Исследование различных свойств К. и д. и построен ие эффективных в определенном смыслекодирований, обладающих требуемыми свойствам и, составляет проблематику теории кодирования. Обычнокритерий эффективности кодиро вания так или иначе связан с минимизацией длин кодовых слов (образов элементов множества А), а требуемые свойства кодирования связаны с обеспечением задан ного уровняпомехоустойчивости, понимаемой в том или ином смысле. В частности, под п омехоустойчивостьюпонимается возможность однозначного декодирования при отсутствии  или допустимом уровне искажений вкодовых словах. Помимо помехоустойчивости, к коди рованию может предъявляться ряд дополнительныхтребований. Напр., при выборе кодиров ания для цифр почтового индекса необходимо согласование собычным способом написани я цифр. В качестве дополнительных требований часто используютсяограничения, связанны е с допустимой сложностью схем, осуществляющих К. и д. Проблематика теориикодирован ия в основном создавалась под влиянием разработанной К. Шенноном (С. Shannon, [1]) тео риипередачи информации. Источником новых задач теории кодирования служат создание и  совершенствованиеавтоматизированных систем сбора, хранения, передачи и обработки инф ормации. Методы решения задачтеории кодирования главным образом комбинаторные, тео ретико­вероятностные и алгебраические.Произвольное кодирование f множества (алфавита ) Асловами в алфавите Вможно распространить намножество А* всех слов в А(сообщений)  следующим образом:  i=1, 2, . . ., k. Такое отображение f: где   наз. побуквенным кодированием с ооб. щений.Более общий класс кодирований сообщений образуют автоматные кодирования,  реализуемые инициальнымиасинхронными автоматами, выдающими в каждый момент вре мени нек­рое (быть может, пустое) слово валфавите В. Содержательный смысл этого обоб щения заключается в том, что автомат в разных состоянияхреализует различные кодирован ия букв алфавита сообщений. Побуквенное кодирование ­ это автоматноекодирование, реа лизуемое автоматом с одним состоянием: Одним из направлений теории кодированияявляе тся изучение общих свойств кодирования и построение алгоритмов распознавания этих сво йств (см.Кодирование алфавитное). В частности, для побуквенных и автоматных кодиров аний найдены необходимыеи достаточные условия для того, чтобы: 1) декодирование было однозначным, 2) существовал декодирующий автомат, т. е. автомат,  реализующийдекодирование с нек­рой ограниченной задержкой, 3) существовал самонастра ивающийся декодирующийавтомат (позволяющий в течение ограниченного промежутка вре мени устранить влияние сбоя во входнойпоследовательности или в работе самого автомата ). Большинство задач теории кодирования сводится к изучению конечных или счетных множе ств слов валфавите В r. Такие множества наз. кодами. В частности, каждому однозначному  кодированию f :  Одноиз основных утверждений теории к ) соответствует код  одирования состоит в том, что условие взаимной однозначностипобуквенного кодирования  (и побуквенному кодированию   накладывает следующее ограничение на длины li=l,if )кодовыхслов f(i): Справедливо и обратное утверждение: если (l0, ..., lm­ 1)­ набор натуральных чисел, удовлетворяющих (1), тосуществует взаимно однозначное поб уквенное кодирование  такое, что слово f(i)имеет длинуli;. При этом, если числ а li упорядочены по возрастанию, то в качестве f(i) можно взять первые после запятой liсим волов разложения числа  в r­ичную дробь (метод Шеннона). Наиболее законченные результаты в теории кодирования связаны с построением эффектив ных взаимнооднозначных кодирований. Описанные здесь конструкции используются на пра ктике для сжатия информациии выборки информации из памяти. Понятие эффективности  кодирования зависит от выбора критериястоимости. При определении стоимости L(f)взаим но однозначного побуквенного кодирования  предполагается, что каждому чис лу  1). Исследованы следующие варианты определения стоимости L(f):  поставлено в соответствие положительное число р i и Р={р 0, ...,Pm­ причем предполагается, что в первых двух случаях р i­ вероятности, с к­рыми некоторый б ернуллиевыйисточник порождает соответствующие буквы алфавита В т   а  в третьем случае р i­заданные длины кодовых слов. При первом определении стоимость рав на средней длине кодового слова, привтором определении с ростом параметра tболее длинн ые кодовые слова оказывают все большее влияние настоимость (  при  при  и  ), при. третьем определениистоимость равна максимальному  превышению длины li кодового слова над заданной длиной р i. Задачапостроения взаимно од нозначного побуквенного кодирования f : В* т­>В*r, минимизирующего стоимость L(f ),равносильна задаче минимизации функции L(f) на наборах (l0, ..., 1 т­ 1 )из натуральных чисел,удовлетворяющих (1). Решение этой задачи известно при каждом и з указанных определений стоимости. Пустьминимум величины L(f)на наборах (l0, . . ., lm­ 1 )из произвольных (не обязательно натуральных) чисел равенLr(P)и достигается на наборе ( l0 (Р), ...,l т­ 1 (Р)). Неотрицательная величина I(f) = L(f) ­ Lr(P)наз.избыточностью, а величина I(f)/L(f)­ о тносительной избыточностью кодирования f. Для избыточности взаимнооднозначного коди построенного по методу Шеннона для дли рования  н  справедливо неравенство I(f)<1. При первом, наиболее употреб ительном,определении стоимости как среднего числа кодовых символов, приходящихся на  одну букву порождаемогоисточником сообщения, величина Lr(P)равна энтропии Шеннона источника, вычисленной по основанию r, a li(P)=­logrpi. Граница избыточности I(f)  = L ср(f)­ Н r(P)<1 может бытьулучшена с помощью так наз. кодирования блоками длины k,  при к­ром сообщения длины k(а не отдельныебуквы) кодируются по методу Шеннона. Изб ыточность такого кодирования не превышает 1/k. Этот же приемиспользуется для эффекти вного кодирования зависимых источников. В связи с тем, что определение длин liпри кодир овании по методу Шеннона основано на знании статистики источника, для нек­рых классов источников разработаны методы построения универсального кодирования, гарантирующего  определеннуюверхнюю границу избыточности для любого источника из этого класса. В час тности, построено кодированиеблоками длины к, избыточность к­рого для любого бернулл иевого источника асимптотически не превышает  х   (при фиксированны ), причем эта асимптотическая граница не может бытьулучшена. продолжение Кодирование и декодорование... Наряду с задачами эффективного сжатия информации рассмотрены задачи оценки избыточ ности конкретныхвидов сообщений. Напр., была оценена относительная избыточность нек­ рых естественных языков (вчастности, английского и русского) в предположении, что текс ты на них порождаются марковскимиисточниками с большим числом состояний. При исследовании задач построения эффективных помехоустойчивых кодирований обычно  рассматриваюткодирования  слов длины пв алфавите В r, и предполагают, чтo буквы  1)}, принадлежащие множеству  алфавита сообщений В т равновероятны.Эффективность такого кодирования оценивают из  к­рым соответствуют коды {f(0), . .., f(m­ быточностью I(f)= п­logrm или скоростью передачи В(f)= При определении помехоустойчивости кодирования формализуется понятие ошибки и вво дитсяв рассмотрение нек­рая модель образования ошибок. Ошибкой типа замещения (или п росто ошибкой) наз.преобразование слова, состоящее в замещении одного из его символов  другим символом алфавита В r.Напр., проведение лишней линии при написании цифры почт ового индекса приводит к замещению в кодовомслове символа 0 символом 1, а отсутствие нужной линии ­ к замещению символа 1 символом 0. Возможностьобнаружения и исправлен ия ошибок основана на том, что для кодирования f, обладающего ненулевойизбыточностью,  декодирование f­1 может быть произвольным образом доопределено на r п ­тсловах из  не являющихся кодовыми. В частности, если множество  я подмножеств D0, . .., Dm­1 таких, что  1 доопределено так, что f­1(Di)=i, то при декодированиибудут исправлены все ошибки, прео бразующие кодовое слово f(i) в Di, i=0, ..., т­ 1. Аналогичная возможностьимеется и в случае ошибок других типов таких, как стирание с имвола (замещение символом другогоалфавита), изменение числового значения кодового с лова на  (арифметическаяошибка), выпадение или вставка символа и т. п. разбито на тнепересекающихс  b=1, ..., r­1, i=0, 1, ...   а декодирование f­ В теории передачи информации (см. Информации передача )рассматриваются вероятност ные моделиобразования ошибок, называемые каналами. Простейший канал     памяти зада ется вероятностями р ijзамещения символа iсимволом j. Для канала определяется величина  (пропускная способность)     без    где максимум берется по всем наборам (q0, . . ., qm­1 )таким, что  Эффективностькодирования f характеризуется скоростью передачи R(f), а помехоустойчив ость ­ средней вероятностьюошибки декодирования Р(f)  (при наилучшем разбиении. В n r на подмножества Di). Основной результат теориипередачи и нформации (теорема Шеннона) состоит в том, что пропускная способность Сявляется верх нейгранью чисел Rтаких, что для любого е>0 при всех п, начиная с нек­рого, существует ко дирование  и     для к­рого  и Р(f)2, а также при r=2 для многих других ти пов ошибок (напр., арифметич.ошибок, выпадений и вставок) не известна (1978). Во втором  случае, когда t=[pn], где р ­ некотороефиксированное число, 0<р<(r­1)/2r, а  "мощностная" граница   где Tr(p)=­p logr(p/(r­ 1))­(1­р)logr(l­ p), существенно улучшена. Имеется предположение, чт о верхняя граница полученная методом случайного выбора кода, является асимптотически точной, т. е. Ir( п,[  рп])~пТ r(2р).Доказательство или опровержение этого предположения ­ одна из центральны х задач теории кодирования. Большинство конструкций помехоустойчивых кодов являются эффективными, когда длин а пкода достаточновелика. В связи с этим особое значение приобретают вопросы, связанны е со сложностью устройств,осуществляющих кодирование и декодирование (кодера и деко дера). Ограничения на допустимый типдекодера или его сложность могут приводить к увел ичению избыточности, необходимой для обеспечениязаданной помехоустойчивости. Напр.,  минимальная избыточность кода в В n 2, для к­рого существует декодер,состоящий из регист ра сдвига и одного мажоритарного элемента и исправляющий одну ошибку, имеетпорядок   (ср. с (2)). В качестве математич. модели кодера и декодера обычно рассматривают с хемы изфункциональных элементов и под сложностью понимают число элементов в схеме.  Для известных классовкодов с исправлением ошибок проведено исследование возможных а лгоритмов К. и д. и получены верхниеграницы сложности кодера и декодера. Найдены такж е нек­рые соотношения между скоростью передачикодирования, помехоустойчивостью код ирования и сложностью декодера (см. [5]). Еще одно направление исследований в теории кодирования связано с тем, что многие резул ьтаты (напр.,теорема Шеннона и граница (3)) не являются "конструктивными", а представл яют собой теоремысуществования бесконечных последовательностей {К п} кодов   В связи с этим предпринимаютсяусилия, чтобы доказать эти результаты в классе  таких последовательностей {К п} кодов, для к­рых существуетмашина Тьюринга, распознаю щая принадлежность произвольного слова длины lмножеству  завремя, имеющее м едленный порядок роста относительно l(напр., llog l). Нек­рые новые конструкции и методы получения границ, разработанные в теории кодирова ния, привели ксущественному продвижению в вопросах, на первый взгляд весьма далеких о т традиционных задач теориикодирования. Здесь следует указать на использование максим ального кода с исправлением одной ошибки васимптотически оптимальном методе реализа ции функций алгебры логики контактными схемами;напринципиальное улучшение верхне й границы для плотности упаковки re­мерного евклидова пространстваравными шарами; на  использование неравенства (1) при оценке сложности реализации формулами одногокласса  функций алгебры логики. Идеи и результаты теории кодирования находят свое дальнейшее  развитие взадачах синтеза самокорректирующихся схем и надежных схем из ненадежных эл ементов. Лит.:[1] Шеннон К., Работы по теории информации и кибернетике, пер. с англ., М., 1963;  [2] Берлекэмп Э.,Алгебраическая теория кодирования, пер. с англ., М., 1971;  [3] Питерсон У., Уэлдон Э., Коды, исправляющиеошибки, пер. с англ., 2 изд., М., 1976;  [4] Дискретная математика и математические вопросы кибернетики, т.1,М., 1974, раздел 5; [5] Бассалыго Л. А., Зяблов В. В., Пинскер М. С,  "Пробл. передачи информации", 1977, т.13, № 3, с. 5­17; [В] Сидельников В. М.,  "Матем. сб.", 1974, т. 95, в. 1, с. 148 ­ 58. В. И. Левенштейн. Математическая энциклопедия.  — М.: Советская энциклопедия. И. М. Виноградов. 1977—1985.  КОДИРОВАНИЕ АЛФАВИТНОЕ  КОЕВКЛИДОВО ПРОСТРАНСТВО См. также в других словарях:  ДЕКОДИРОВАНИЕ — см. Кодирование и декодирование …   Математическая  энциклопедия  Кодирование звуковой информации — Эту статью следует викифицировать.  Пожалуйста, оформите её согласно правилам оформления статей. В основе  кодирования звука с использованием ПК лежит процесс преобразования колебаний  воздуха в колебания электрическог …   Википедия  КОДИРОВАНИЕ — (от франц. code – свод законов, правил) – отображение  (преобразование) нек рых объектов (событий, состояний) в систему конструктивных  объектов (называемых кодовыми образами), совершаемое по определ. правилам,  совокупность к рых наз. шифром К.,… …   Философская энциклопедия  КОДИРОВАНИЕ ИНФОРМАЦИИ — установление соответствия между  элементами сообщения и сигналами, при помощи к рых эти элементы могут быть  зафиксированы. Пусть В, , множество элементов сообщения, А алфавит с  символами , Пусть конечная последовательность символов наз. словом в… …   Физическая энциклопедия  КОДИРОВАНИЕ ОПТИМАЛЬНОЕ — (в инженерной психологии) (англ. optimal  coding) создание кодов, обеспечивающих максимальную скорость и надежность  приема и переработки информации об объекте управления человеком оператором  (см. Прием информации, Декодирование). Проблема К. о.… …   Большая  психологическая энциклопедия  ДЕКОДИРОВАНИЕ (в инженерной психологии) — (англ. decoding)  заключительная операция процесса приема информации человеком оператором,  состоящая в перешифровке параметров, характеризующих состояние объекта  управления, и в переводе их в образ управляемого объекта (см. Кодирование… …   Большая психологическая энциклопедия  Декодирование — [decoding] восстановление сообщения, закодированного  переданными и принятыми сигналами (см. Кодирование) …   Экономико­ математический словарь  КОДИРОВАНИЕ — КОДИРОВАНИЕ. Один из этапов порождения речи, в то  время как «декодирование» – прием и интерпретация, процесс понимания речевого  сообщения. См. психолингвистика …   Новый словарь методических терминов и  понятий (теория и практика обучения языкам)  КОДИРОВАНИЕ — (англ. coding). 1. Преобразование сигнала из одной  энергетической формы в др. 2. Преобразование одной системы сигналов или знаков в др., что часто называется также «перекодированием», «сменой кода» (для речи  «перевод»). 3. К. (мнемическое)… …   Большая психологическая энциклопедия  Декодирование — Эта статья о коде в теории информации, другие значения этого  слова см. в код (значения). Код  правило (алгоритм) сопоставления каждому  конкретному сообщению строго определённой комбинации символов (знаков) (или  сигналов). Кодом также называется… …    Оптимальное кодирование Одно и то же сообщение можно закодировать различными способами. Оптимально  закодированным будем считать такой код, при котором на передачу сообщений  затрачивается минимальное время. Если на передачу каждого элементарного символа (0  или 1) тратиться одно и то же время, то оптимальным будет такой код, который будет  иметь минимально возможную длину. Пример 1. Пусть имеется случайная величина  X(x1,x2,x3,x4,x5,x6,x7,x8), имеющая восемь состояний  с  распределением вероятностей Для кодирования алфавита из восьми букв без учета вероятностей равномерным двоичным  кодом нам понадобятся три символа:    Это         000, 001, 010, 011, 100, 101, 110, 111 Чтобы ответить, хорош этот код или нет, необходимо сравнить его с оптимальным  значением, то есть определить энтропию Определив избыточность L по формуле L=1­H/H0=1­2,75/3=0,084,  видим, что возможно  сокращение длины кода  на 8,4%. Возникает вопрос: возможно ли составить код, в котором на одну букву будет, в среднем  приходится меньше элементарных символов. Такие коды существуют. Это коды Шеннона­Фано и Хаффмана. Принцип построения оптимальных кодов: 1.   Каждый элементарный символ должен переносить максимальное количество  информации, для этого необходимо, чтобы элементарные символы (0 и 1) в  закодированном тексте встречались в среднем одинаково часто. Энтропия в этом случае  будет максимальной. 2.   Необходимо буквам первичного алфавита, имеющим большую вероятность,  присваивать более короткие кодовые слова вторичного алфавита.