Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ЛЕКЦИЯ 15, 16
Код, кодирование, кодовые сигналы.
Кодом называется форма представления сообщений, в которой реализуются определенные правила, обеспечивающие соответствие между кодовыми символами и кодируемыми сообщениями.
Кодирование – это операция перевода по определенным правилам формального объекта, выраженного совокупностью кодовых символов одного алфавита, в формальный объект, выраженный символами другого алфавита.
Кодовым сигналом называют сигнал, каждый элемент которого служит для отображения данного элемента кодируемого сообщения или числа.
Примеры кодирования – перевод текста (формального) объекта с одного языка на другой; использование машинных языков – Фортран, Алгол и т.д.
При кодировании используются в качестве символов буквы алфавита, цифры в определенной системе счисления, различные условные знаки.
Коды в информационно-измерительной технике применяются при кодовом представлении результата измерения для цифровой обработки, а также при передаче результатов измерения и других сообщений по каналам связи. Наиболее широкое применение получило числовое кодирование, являющееся операцией отображения объекта числами. В процессе измерения определяется значение физической величины, состоящее из ее числового значения и единицы. Числовое кодирование в измерении является операцией отображения количества единиц данной величины Nx числом в определенной системе счисления.
Числовым кодом называют форму представления числа удобную для различных дискретных устройств.
Системы счисления.
Системой счисления называют совокупность символов в виде цифровых знаков и правил, применяемых для однозначного представления чисел.
Системы счисления предназначаются для выражения количественной информации в цифровой форме и подразделяются на позиционные и непозиционные.
В непозиционных системах счисления количество цифровых знаков неограниченно и значение (“вес”) каждого знака не зависит от его положения по отношению к другим знакам в представлении данного числа.
Простейшей непозиционной системой счисления является единичная N1, в которой данное целое число изображается в виде повторения одного знака с весом, равным единице, нужное число раз.
Например, число 8 изображается 11111111. Для выражения больших чисел она неудобна, слишком громоздка.
Более удобно и компактно числа выражаются в позиционных системах счисления. Наиболее распространены двоичная, восьмеричная, шестнадцатеричная и десятичная системы счисления. В десятичной системе есть десять разных знаков – 0,1,2,3,4,5,6,7,8,9, изображающих числовые значения от нуля до девяти. В двоичной системе – только два знака – 0 и 1 (нуль и один). В восьмеричной и шестнадцатеричной системах – аналогично 8 и 16 знаков (0,1,2,3,4,5,6,7 и 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F).
В общем случае в позиционной системе счисления любое целое число N можно выразить в следующей форме
(1)
Символ “B” обозначает основание системы и равен числу знаков в данной системе; символ “n” обозначает номер размера данного числа; символы являются знаками или цифрами данной системы счисления, стоящими в соответствующем разряде каждого числа.
Используя формулу (1), представим для примера число N=76, в десятичной и двоичной системах:
N=7101+6100=76
N=126+225+024+123+122+021+020=100 100=76
Наибольшее значение числа, которое может быть выражено в данной системе счисления при данном количестве разрядов “l”,
(2)
Число разрядов или знаков необходимое для представления числа
(3)
Важным преимуществом двоичной системы счисления является то, что она основана на использовании элементов, имеющих только два различных состояния, а такие элементы наиболее просты и наиболее надежны.
Неудобство двоичной системы – неудобство визуальной индикации и цифровой реализации числа.
Числовые коды.
Числовым кодом называют форму представления числа, удобную для различных дискретных устройств.
Каждый числовой код состоит из отдельных элементов или сигналов. Если в коде данный элемент имеет в любом числе одинаковые числовые значения или вес, то такой код называют взвешенным. Используемые коды делятся на числоимпульсные, использующие единичную систему счисления и цифровые – десятичный, двоичный, двоично-десятичный и др.
В зависимости от способа выдачи информации цифровые коды делятся на параллельные, в которых все разряды числа выдаются одновременно по соответствующему числу каналов или по одному каналу частотным разделением, и последовательные, в которых сигналы по разрядам числа выдаются поочередно в соответствующие каналы или с временными промежутками в один канал.
Число возможных сигналов в коде определяется формулой
N=Bn, (4)
Где В – основание системы счисления, n – число элементов (разрядов) кода, причем
(5)
Для двоичного кода; ; .
Сравнивая различные системы счисления с точки зрения удобства физической реализации соответствующих им логических элементов и простоты выполнения в них арифметических и логических действий, предпочтение необходимо отдать двоичной системе. Логические элементы, соответствующие этой системе, должны иметь всего два устойчивых состояния. Однако он неудобен при вводе и выводе информации, так как трудно оперировать с непривычными двоичными числами. Поэтому, помимо двоичной получили распространение системы, которые с одной стороны легко сводятся как к двоичной, так и к десятичной системе, а с другой стороны дают более компактную запись.
Чтобы сохранить преимущества двоичной системы и удобство десятичной, используют двоично-десятичные коды. В таком коде каждую цифру десятичного числа записывают в виде четырехразрядного двоичного числа (тетрады). С помощью 4 разрядов можно образовать 16 различных комбинаций, из которых любые 10 могут составить двоично-десятичный код. Наиболее целесообразным является код 8-4-2-1 (табл.1). Этот код относится к числу взвешенных кодов. Цифры в названии кода означают вес единиц в соответствующих двоичных разрядах.
В таблице 1 представлены два других двоично-десятичных кода с весами 5-1-2-1 и 2-4-2-1, которые широко не пользуются при поразрядно уравновешивании в цифровых измерительных приборах.
Таблица 1.
|
Число в десятичном коде |
Число в двоичном коде |
Число в равномерном двоичном коде |
Число в коде Грея |
Число в двоично-десятичном коде с весами |
Число в двоично-десятичном коде с весами |
Число в двоично-десятичном коде с весами |
|
0 |
0 |
0000 |
0000 |
0000 0000 |
0000 0000 |
0000 0000 |
|
1 |
1 |
0001 |
0001 |
0000 0001 |
0000 0001 |
0000 0001 |
|
2 |
10 |
0010 |
0011 |
0000 0010 |
0000 0010 |
0000 0010 |
|
3 |
11 |
0011 |
0010 |
0000 0011 |
0000 0011 |
0000 0011 |
|
4 |
100 |
0100 |
0110 |
0000 0100 |
0000 0111 |
0000 0100 |
|
5 |
101 |
0101 |
0111 |
0000 0101 |
0000 1000 |
0000 1011 |
|
6 |
110 |
0110 |
0101 |
0000 0110 |
0000 1001 |
0000 1100 |
|
7 |
111 |
0111 |
0100 |
0000 0111 |
0000 1010 |
0000 1101 |
|
8 |
1000 |
1000 |
1100 |
0000 1000 |
0000 1011 |
0000 1110 |
|
9 |
1001 |
1001 |
1101 |
0000 1001 |
0000 1111 |
0000 1111 |
|
10 |
1010 |
1010 |
1111 |
0001 1010 |
0001 0000 |
0001 0000 |
|
11 |
1011 |
1011 |
1110 |
0001 1011 |
0001 0001 |
0001 0001 |
|
12 |
1100 |
1100 |
1010 |
0001 1100 |
0001 0010 |
0001 0010 |
|
13 |
1101 |
1101 |
1011 |
0001 1101 |
0001 0011 |
0001 0011 |
|
14 |
1110 |
1110 |
1001 |
0001 1110 |
0001 0111 |
0001 0100 |
|
15 |
1111 |
1111 |
1000 |
0001 1111 |
0001 1000 |
0001 1011 |
Коды используемые для передачи бывают равномерные и неравномерные.
В равномерных кодах все комбинации состоят из одинакового числа символов (n), т.е. имеют одинаковую длину. При одинаковой длине кодовых комбинаций облегчается определение границ каждой из них, которое производится путем подсчета числа символов.
В неравномерных кодах необходимо различие кодовых комбинаций предусматривать специальные разделительные символы.
Среди кодов, отходящих от систем счисления, большое практическое значение имеют такие, у которых при переходе от одного числа к другому изменение происходит только в одном разряде.
Наибольшее распространение получил код Грея, часто называемого циклическим или рефлексно-двоичным. Код Грея используют в технике аналого-цифрового преобразования, где он позволяет свести к единице младшего разряда ошибку неоднозначности при считывании. Комбинации кода Грея приведены в таблице 1.
Правила перевода из кода Грея в обычный двоичный сводятся к следующему: первая единица со стороны старших разрядов остается без изменения, последующие цифры (0 или 1) остаются без изменения, если число единиц им предшествующих, четно, инвертируются, если число единиц нечетно.
В коде Грея элементы расположены таким образом, что в любом из переходных положений меняются только в одном разряде.
Для устранения погрешности считывания применяют также сдвоенные счеты или метод V-развертки.
Коды не обнаруживающие возникающих искажений.
Существует принципиальная разница при кодировании информации в условии отсутствия помех и при наличии последних. В условиях отсутствия помех используются коды не обнаруживающие ошибку, т.е. не обнаруживающие возникающие вследствие ее искажения. При образовании сигнала в этих кодах не вносится никаких ограничений, поэтому эти коды называются кодами на все сочетания. Если используется “B” признаков посылок (основание системы счисления), то число образуемых сигналов равно
где n – число элементов кода.
Для двоичной системы
Т.к. в случае применения рассматриваемого кода используются все возможные комбинации, “n” является минимальным числом символов в закодированном сигнале, с помощью которых можно построить комбинации для передачи N сигналов при принятом числе возможных значений символов B.
Классический пример кода на все сочетания – двоичный код (код Грея также). В нем кодовые комбинации отличаются одна от другой не менее чем одним элементом.
Избыточные коды.
Кодирование в условиях помех.
Коды обнаруживающие ошибки.
Для повышения надежности используются коды, обеспечивающие получение помехоустойчивых сигналов.
Одним из путей обеспечения помехоустойчивости сигналов является выбор из общего возможного числа кодовых комбинаций лишь тех, которые отличаются друг от друга не менее чем двумя элементами. При этом искажения сигнала в одном элементе легко обнаруживается, вследствие чего наступает защитный отказ.
К такого рода кодам относится, например, коды на одно сочетание, когда используются только кодовые комбинации, содержащие постоянное число k (k<n) элементов с определенным признаком.
Число возможных кодовых комбинаций (сигналов) в этом случае определяется числом сочетаний из n элементов по k
Наибольшее число комбинаций можно получить, если при четном “n” принять или при нечетном “n” принять .
Если, например, n=4, то k=2 и
Если бы при n=4 сигналы формировались по коду на все сочетания, то имелись бы 16 сигналов, представленных в табл.1.
В случае использования кода на одно сочетание при k=2 из 16 комбинаций выбираются только 6, содержащие по два символа со значением 1.
3. 0011 9. 1001
6. 0110 12.1100
Каждый сигнал отличается от любого другого сигнала не менее чем двумя элементами. Искажение любого сигнала в одном элементе приводит к образованию кодовой комбинации, не соответствующей принципу построения кода. Такой искаженный сигнал не будет воспринят ни одной из исполнительных цепей.
При анализе кода на одно сочетание видно определенное недоиспользование возможностей кодирования: с помощью 4 элементов, применяя код на все сочетания, можно сформировать не 6, а 16 сигналов. Для формирования же 6 сигналов в этом случае было бы достаточно всего 3 элементов, т.к.
Таким образом, код на одно сочетание обладает некоторой избыточностью.
Информационная способность кода и избыточность.
Получатель сообщения в каком-либо коде не знает, какой из символов к нему поступит, поэтому сообщения (сигналы) в любом коде можно рассматривать как системы со многими случайными состояниями. Число возможных состояний равно числу всех различимых сигналов (символов) кода. Это дает возможность говорить об энтропии кода. Если считать, что все N символов (сигналов) кода при передаче сообщений могут появляться с равной вероятностью, то вероятность каждого их них будет .
Основная теорема Шеннона о кодировании для канала с помехами.
Теорема помехоустойчивого кодирования базируется на результатах исследований проведенных Шенном и сформулированных им в виде теоремы:
Анализ теоремы. Теорема устанавливает теоретический предел возможной эффективности системы при достоверной передачи информации. Ею опровергнуто представление о том, что достижение сколь угодно малой вероятности ошибки в случае передачи информации по каналу с помехами, возможно лишь при введении бесконечно большой избыточности, т.е. при уменьшении скорости передачи до нуля. Из теоремы следует, что помехи в канале не накладывают ограничений на точность передачи. Ограничение накладывается только на скорость передачи, при которой может быть достигнута сколь угодно высокая достоверность передачи.
Теорема неконструктивна: в ней не затрагивается вопрос о путях построения кодов.
Следует отметить, что при любой конечной скорости передачи информации вплоть до пропускной способности сколь угодно малая вероятность ошибки достигается лишь при безграничном увеличении длительности кодируемых последовательностей знаков. Не исключено, конечно, вероятность, что искаженный в нескольких элементах сигнал 1 или сигнал 3, но вероятность искажения сигнала в нескольких элементах значительно меньше, чем в одном.
Для выполнения коррекции единичного искажения необходимо построить цепи расшифровки таким образом, чтобы исполнительный срабатывал как при приеме неискаженного сигнала, так и при приеме сигналов, отличающихся от основного одним элементом.
Рассматриваемый код обладает значительной избыточностью
,
т.е. 3 элемента из 5 несут контрольные и корректирующие функции, не обеспечивая передачу информации.
Общее число элементов n корректирующего кода определяется как сумма рабочих (информационных) элементов n0 и контрольных элементов k:
n = n0+k.
Полное число комбинаций 2n. Основной сигнал и его искажения в одном элементе занимает n+1 комбинаций. Отсюда количество возможных колебаний кода обнаруживающего и исправляющего единичную ошибку определяется неравенством
Из неравенства при заданном N определяются n0, n и затем k.
Число элементов, в которых одна кодовая комбинация должна отличаться от другой, или, как говорят, число переходов определяется по формуле
d=r+s+1,
где r – число обнаруживаемых ошибок; s – число исправляемых ошибок.
Пример кода с автоматическим исправлением ошибок рассмотрим на практическом занятии.
В заключении приведем основную теорему Шеннона о кодировании для канала с помехами.
В качестве примера рассмотрим определение избыточности приведенного ранее n-элементарного (n=4) кода на одно сочетание (k=2), обеспечивающего 6 комбинаций.
, округляем до n0=3.
Тогда
Это означает, что ¼ от элементов в коде на одно сочетание является избыточной, не выполняет функций передачи информации. Введение их вызвано не требованиями кодирования, а стремлением повысить помехоустойчивость сигнала.
Коды с коррекцией искажений.
Если сигналы составлены таким образом, что один отличается от другого не менее чем тремя элементами, то при искажении одного элемента какого-либо сигнала можно установить, какой сигнал был первоначально послан, т.к. искаженный в одном элементе сигнал будет отличаться от посланного одним элементом, а от всех остальных – минимум двумя элементами.
Это дает возможность скорректировать искаженный в одном элементе сигнал и реализовать его как правильный.
В качестве примера рассмотрим систему пятиэлементных кодовых комбинаций, отличающихся друг от друга не менее чем 3 элементами
Пусть принят сигнал, соответствующий кодовой комбинации 01011. Такой комбинации в списке нет, следовательно это искаженный сигнал. Он отличается от первой комбинации двумя элементами, от второй – одним элементом, от третьей – тремя и от четвертой – четырьмя элементами.
Вывод: скорее всего это сигнал 2, искаженный в одном элементе.
Тогда энтропия кода:
Справка. При равных вероятностях Pi всех n состояний энтропия равна
но , тогда
- формула Хартли
Сигнал (символ) любого числового кода на все сочетания несет информацию
где В – основание системы счисления, n – число элементов в сигнале (символе).
Избыточность кода D определяется выражением
(6)
Н – энтропия данного кода, имеющего N сигналов
Н=logN
Минимальное число элементов сигнала, необходимое для образования N комбинаций, как и в рассматриваемом коде
(7)
Иначе
(8)
Hmax – максимальное число сигналов (символов, комбинаций), которые можно организовать из элементов данного кода (фактически это код на все сочетания)
(9)
где n – число элементов сигнала (символа) данного кода.
Тогда
(10)
Отметим, что, как правило, если n0 получается дробным, его округляют до целого числа в большую сторону.
Таким образом, безошибочные передачи при наличии помех возможны лишь теоретически.
Обеспечение передачи информации с весьма малой вероятностью ошибки и достаточно высокой эффективностью возможно лишь при кодировании чрезвычайно длинных последовательностей знаков. На практике степень достоверности и эффективности ограничивается двумя факторами: размерами и стоимостью аппаратуры кодирования и декодирования и временем задержки передаваемого сообщения.
Литература
85