Теория кодирования

Министерство  образования и науки Российской Федерации

Южно-Уральский  Государственный университет

Приборостроительный факультет

Кафедра Автоматики и Управления

 

 

 

 

 

 

 

 

РЕФЕРАТ

 

На тему: «Теория кодирования»

По дисциплине: «Общая теория связи»

 

    

 

 

 

 

 

 

СОСТАВИЛ

Студент группы ПС-317

____________ Коченгин  А.Е 

 

 

ПРОВЕРИЛА

                        Барбасова Т.А 

«___»_________ 2013г.

 

 

 

 

 

 

 

 

 

Челябинск – 2013

 

Содержание

 

1.Основные понятия и  определения теории кодирования………………….3

2. Двоичный код на  все сочетания…………………………………………......4

3. Единично-десятичный код…………………………………………………...4

4. Двоично-десятичный код…………………………………………………......5  5.Число-импульсный код………………………………………………………..8

6. Код Морзе……………………………………………………………………….8

7.Код Бодо………………………………………………………………………...11

8 . Международный телефонный  код………………………………………....12

9. Код Грэя………………………………………………………………………..14

3. ПОМЕХОЗАЩИЩЕННЫЕ КОДЫ

3.1 Основные понятия…………………………………………………………...16

3.2 Коды с обнаружением  ошибок……………………………………………...20

3.3Коды с постоянным  числом единиц и нулей в  комбинациях…………..23

3.4.Распределительный  код……………………………………………………..25

3.5. Код с проверкой на четность…………………………………………….....25

3.6. Код с числом единиц кратным  трем……………………………………....28

3.7. Код с удвоением элементов(корреляционный  код)…………………......28

3.8. Инверсный код………………………………………………………………..29

3.9. Код Хэмминга………………………………………………………………....30

3.10. Циклические коды………………………………………………………….36

3.11. Итеративные коды………………………………………………………….43

 

 

 

1. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ  ТЕОРИИ КОДИРОВАНИЯ

Код — это набор условных обозначений (или сигналов) для записи (или передачи) некоторых заранее определенных понятий.

Кодирование информации – это процесс формирования определенного представления информации. В более узком смысле под термином «кодирование» часто понимают переход от одной формы представления информации к другой, более удобной для хранения, передачи или обработки.

Обычно каждый образ при кодировании (иногда говорят — шифровке) представлении  отдельным знаком.

Знак - это элемент конечного множества отличных друг от друга элементов.

Знак вместе с его смыслом  называют символом.

Набор знаков, в котором определен  их порядок, называется алфавитом. Существует множество алфавитов:

• алфавит кириллических букв {А, Б, В, Г, Д, Е, ...}
• алфавит латинских букв {А, В, С, D, Е, F,...}
• алфавит десятичных цифр{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
• алфавит знаков зодиака {картинки знаков зодиака} и др.

Особенно большое значение имеют  наборы, состоящие всего из двух знаков:

• пара знаков {+, -}
• пара цифр {0, 1}
• пара ответов {да, нет}

Алфавит, состоящий из двух знаков, называется двоичным алфавитом. Двоичный знак (англ. binary digit) получил название «бит».

Шифрование - кодирование сообщения отправителя, но такое чтобы оно было не понятно несанкционированному пользователю.

Длиной кода называется такое количество знаков, которое  используется при кодировании.

Количество символов в алфавите кодирования и длина кода - совершенно разные вещи. Например, в русском  алфавите 33 буквы, а слова могут  быть длиной в 1, 2, 3 и т.д. буквы.

Код может быть постоянной и непостоянной длины. Коды различной (непостоянной) длины  в технике используются довольно редко. Исключением является лишь троичный код Морзе. В вычислительной технике  в настоящее время широко используется двоичное кодирование с алфавитом (0, 1). Наиболее распространенными кодами являются ASCII (American standart code for information interchange - американский стандартный код для обмена информацией) и КОИ-8 (код обмена информации длиной 8 бит).

2. Двоичный код на все сочетания

Отличительный особенностью непомехозащищенных кодов  является наличие в их составе  кодовых комбинаций, которые отличаются друг от друга лишь в одном разряде. Типичным кодом такого типа является двоичный код на все сочетания.

Например, комбинации 0010 и 0011 отличаются друг от друга лишь в младшем разряде. Если помеха исказит первую комбинацию, то будет принят сигнал 0011 и будет  принят сигнал и будет неясно, то ли пришла первая искаженная комбинация, то ли принята вторая неискаженная. Можно найти еще целый ряд  комбинаций в том же коде, которые  отличаются друг от друга только в  одном разряде. Комбинации 0101 и 0111 - в 2-ом разряде комбинации 1110 и 0110 - в 4ом разряде и т.д. Есть различия в  двух и больше разрядах, например, комбинации 1111 и 0001. Есть для каждой комбинации соседние комбинации, отличающиеся на один разряд: для 1111 имеем 0111, 1110, 1101, 1011. Все это делает двоичный код на все сочетания непомехозащищенным. Непомехоустойчивым или непомехозащищенным кодом называется код, в котором  искажение одного разряда кодовой  комбинации не может быть обнаружено. Иногда эти коды называются обыкновенными  кодами. Рассмотрим примеры двоичных непомехозащищенных кодов.

Двоичный код на все  сочетания - код полностью выражающийся двоичной системой счисления. Общее число комбинаций N = 2ⁿ.

3. Единично-десятичный код

Единично-десятичный код предусматривает передачу разрядов десятичных цифр соответствующим количеством единиц. 

Недостатком единично-десятичного кода является его информационная неэкономичность. Так, например, при двухразрядном единично-десятичном коде необходимо передать 18 элементов кода и при этом на один элемент приходится приблизительно 5 значений измеряемой величины. Информационная неэкономичность кода приводит к увеличению времени передачи измерительной информации.

Важным  преимуществом единично-десятичного кода является упрощение приемника с цифровой формой отчета или регистрации.

Каждый разряд десятичного числа  записывается в виде соответствующего числа единиц. При этом разряды  разделяются интервалами. Этот код  неравномерный, хотя и может быть преобразован в равномерный путем  приписывания в каждом разряде слева  нулей, доводящих общее число  символов в каждом разряде до 10.

11 111 1111 – 234

111 11111 11 – 352

 

Например, в первой строке записано число 234, при  записи равномерным кодом оно  примет вид

0000000011 00000000111 0000001111

 

4. Двоично-десятичный код

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

Таблица 1.2

Наиболее естественным и популярным считается код прямого замещения, в котором каждая цифра десятичного  числа заменяется соответствующим  четырехразрядным двоичным числом. Его другое название код 8421 отражает значение весовых множителей, приписываемых соответствующим битам в кодирующей группе, в связи с чем он называется также взвешенным кодом. Удобства этого кода проявляются при машинном переводе из десятичной системы в двоичную и обратно, а также при суммировании на обычных двоичных сумматорах благодаря его аддитивности (сумма кодов двух цифр представляет код суммы).

Избыточность тетрады, допускающей 16 кодовых комбинаций, позволяет  создавать и другие варианты двоично-десятичных кодов с использованием четверки битов на десятичный разряд.

Одни из них код 2421 также взвешенный, но старший разряд имеет вес не 8, а 2. Его положительная особенность  состоит в том, что замена в  кодирующей тетраде нулей на единицы, а единиц на нули превращает каждую десятичную цифру х в 9-х, т. е. получается обратный код. Для превращения его в дополнительный код достаточно прибавить единицу. Коды с таким свойством называют самодополнительными. Они применяются при выполнении арифметических операций над десятичными числами в обратном или дополнительном коде.

Самодополнительным является и  код с избытком 3, который получается прибавлением  к каждой цифре кода прямого замещения. Как и код 2421, он удобен для выполнения операций над десятичными числами. При этом легко определяется перенос, так как сумма двух слагаемых, каждое из которых берется с избытком 3, получится с избытком 6, что исключает лишние кодовые комбинации (для получения правильного кода суммы из полученного результата вычитается 3). Но этот код в отличие от кодов 8421 и 2421 не является взвешенным, вследствие чего мало удобен для преобразования чисел из одной системы в другую.

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

Так, в коде 2 из 5 каждая десятичная цифра представляется пятью разрядами, из которых два и только два  содержат единицы. Если появится ошибка в одном из двоичных разрядов, т. е. если нуль превратится в единицу  или единица превратится в  нуль, то общее число единиц окажется больше или меньше двух, что можно  обнаружить простым их подсчетом. Другой способ обнаружения одиночной ошибки основан на использовании бита, которым  дополняется какой-либо код, для  контроля четности. Значение дополнительного  бита выбирается таким, чтобы общее  число единиц в кодирующей группе всегда было четным или нечетным (в  зависимости от принятого правила  контроля). Рассмотренные способы  обнаруживают одиночные ошибки, точнее, нечетное количество ошибок, по не реагируют  на двойные и вообще четное количество ошибок. Существуют более сложные  способы построения корректирующих кодов, используемых в технике связи, но в обычных вычислительных системах из-за громоздкости они не применяются.

Операции над десятичными числами  выполняются с помощью несколько  дополненной двоичной арифметики. Так, при сложении двух чисел в коде прямого замещения 8421 необходимо добавить корректирующее слагаемое  к каждой тетраде, в которой в процессе суммирования получена недопустимая цифра (1010, 1011, 1100, 1101, 1110) или возник перенос в следующую тетраду. Например:

При вычитании чисел в коде 8421 коррекция сводится к вычитанию  , из каждой тетрады разности, которая потребовала заем. Например:

5. Число-импульсный код

Иногда  его называют единичным или унитарным  кодом. Кодовые комбинации отличаются друг от друга числом единиц.

00000 - пример пятиразрядного кода. Очевидно N = n

10000

11000

11100

11110

11111

В цифро-аналоговых преобразователях используют число-импульсный код, в котором число импульсов равно изображаемому числу. Так как передача число-импульсного кода по каналу связи занимает много времени, то обычно информация во всех частях системы выражается в виде двоичного или двоично-десятичного кодов и только в цифро-аналоговых преобразователях двоичный код преобразуется в число-импульсный. Преобразование число-импульсного кода в двоичный выполняется двоичным счетчиком.

6. Код Морзе

Относится к числу неравномерных кодов, в которых кодовые комбинации отличаются различной длительностью. В коде Морзе сигналы (буквы и  цифры, условные знаки) передаются в  виде точек и тире. Точка может  быть записана как 1 и передаваться одним импульсом. Тире записывается тремя строчными импульсами (без  интервала между ними). Интервал между точкой и тире означает нули. Одна кодовая комбинация (буква или  цифра) отдельна от другой интервалом из совокупности трех нулей. Если длительности 1 и 0 одинакова и равны τ, то самая  короткая комбинация (буква Е) по продолжительности  равна 4τ, а самая длительная - 22 τ (цифра 0). В среднем длина кодовой  комбинации равна примерно 9, 5τ.

Различная длина кодовых комбинаций при  передаче букв и цифр

А - 10111 (· - ) является недостатком кода Морзе, впервые

Н - 11101 ( - ·) примененного в 1844 году.

С - 10101 (· · ·)

Т - 111 (-)

1 - 1011101110111 (· - - - )

5 - 101010101 (· · · · ·)

Азбука Морзе – CW от continuous wave - незатухающая волна

Азбука Морзе, код Морзе, «Морзянка» — способ кодирования букв алфавита, цифр, знаков препинания и других символов при помощи длинных и коротких сигналов, так называемых «тире» и «точек» (а также пауз, разделяющих буквы). За единицу времени принимается длительность одной точки. Длительность тире равна трём точкам. Пауза между знаками в букве — одна точка, между буквами в слове — 3 точки, между словами — 7 точек.  
Была названа в честь американского изобретателя Сэмюеля Морзе, который изобрёл её в 1838.  
Если же говорить о самой телеграфной азбуке (системе кодировки символов короткими и длинными посылками для передачи их по линиям связи, известная как «код Морзе» или «морзянка»), которую применяют сейчас, существенно отличается от той, что изобрел в 1838 г. С.Морзе, хотя некоторые исследователи полагают, что ее автором был Альфред Вейль — партнер Сэмюеля Морзе по бизнесу. Надо заметить, что исходная таблица «кода Морзе» разительно отличалась от тех кодов, что сегодня звучат на любительских диапазонах. В ней, во-первых, использовались посылки трех разных длительностей («точка», «тире» и «длинное тире» — в 4 раза длиннее «точки»). Во-вторых, некоторые символы имели паузы внутри своих кодов.  
Азбука Морзе является первым цифровым способом передачи информации. Телеграф и радиотелеграф первоначально использовали азбуку Морзе; позже стали применяться код Бодо и ASCII, которые более удобны для автоматизации. Впрочем, сейчас и для азбуки Морзе есть средства автоматической генерации и распознавания.  
Для передачи русских букв использовались коды сходных латинских букв; это соответствие алфавитов позже перешло в МТК-2, а потом в КОИ-7 и КОИ-8 (однако в азбуке Морзе букве Q соответствует Щ, а в МТК и КОИ — Я).  
достоинство кода:  
- высокая помехозащищенность при приеме на слух в условиях сильных радиопомех;  
- возможность кодирования вручную;  
- запись и воспроизведение сигналов простейшими устройствами.  
недостатки кода:  
- неэкономичность, на передачу одного знака кода требуется в среднем 9,5 элементарных посылок;  
- малая пригодность для буквопечатающего приема;  
- низкая скорость телеграфирования