Эскорт-услуги в Москве от Queens Palace


GOUSPO студенческий портал!

форум, учебники, лекции, и многое другое

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

Тема 8. Элементы теории и практики кодирования

План:

1. История кодирования и защиты информации

2. Системы счисления для представления информации в ЭВМ

3. Вероятностная теория информации

4. Понятие кодирования информации

5. Системы контроля кодирования

6. Кодирование и обработка чисел компьютером

Цель. Знакомство с теоретическими предпосылками теории кодирования, с основными понятиями теории кодирования,  соответствующими теоремами Шеннона. Обучение записи чисел в системах счисления с основаниями 2,8, 16.  Формирование представлений о кодировании информации компьютером.

Теоретические сведения.

Язык дан для того, чтобы скрывать свои мысли.

Народная мудрость

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

Объектом кодирования служит как дискретная, так и непре­рывная информация, которая поступает к потребителю через ис­точник информации. Понятие кодирование означает преобразова­ние информации в форму, удобную для передачи по определен­ному каналу связи.

Обратная операция - декодирование - заключается в восста­новлении принятого сообщения из закодированного вида в обще­принятый, доступный для потребителя.

1. История кодирования и защиты информации.

С глубокой древности люди искали эффективные способы передачи информации:

~       Движение факелов использовал древнегреческий историк Полибий (II в. Дон.э.};

~       Оптический телеграф семафор впервые использовал Клод Шапп в 1791 г.;

~       Движение электромагнитной стрелки в электромагнитных телеграф­ных аппаратах впервые применили русский физик П.Л. Шиллинг (1832) и профессора Гёттингенского университета Вебер и Гаусс (1833);

~       Азбука и телеграфный аппарат Самюэла Морзе (1837);

~        Международный флажковый код для передачи информации опти­ческими сигналами впервые ввел капитан Фредерик Марьят в 1861 г. На основе свода корабельных сигналов;

~       Беспроволочный телеграф (радиопередатчик) был изобретен А.С.Поповым в 1895 г. И Маркони в 1897 г. Независимо друг от друга;

~       Беспроволочный телефон, телевидение (1935), затем и ЭВМ но­вые средства связи, появившиеся в XX в., с которыми связана новая эпоха в информатизации общества.

Одновременно с потребностью передавать информацию люди искали способы скрыть смысл передаваемых сообщений от посторонних любо­пытных глаз. Императоры, торговцы, политики и шпионы искали спосо­бы шифрования своих посланий. Образцы тайнописи можно встретить еще у Геродота (V в. до н. э.).

К тайнописи криптографии прибегал Гай Юлий Цезарь, заменяя в своих тайных записях одни буквы другими. Использовали шифрование не только древнегреческие жрецы, но и ученые Средневековья: математики итальянец Джероламо Кардано и француз Франсуа Виет, нидерландский гуманист, историк, юрист Гроций, выдающийся английский философ Фрэнсис Бэкон. Од­нако отцом криптографии считается архитектор Леон Баттиста Альберти (1404-1472), который ввел шифрующие коды и много алфавитные под­становки.

Первые манипуляции с символами в виде различных кодов возникли с потребностью шифровать информацию.

Знания математики нужны для того, чтобы найти простую, но надежную систему кодирования, недоступную для расшифровки посторонним лицам, а так же найти способы деко­дирования чужой системы тайнописи, чужих кодов.

Например, механическая замена одних букв или чисел другими подстановки Цезаря достаточно легко поддается дешифровке. Причем сам процесс декодирования аналогичен решению неопределенных урав­нений со многими неизвестными.

Сэр Фрэнсис Бэкон (1561 1626), английский писатель и философ, лорд-канцлер елизаветинской эпохи, автор двух литерного кода, доказал в 1580 г., что для передачи информации достаточно двух знаков. Ф.Бэ­кон сформулировал требования к шифру.

1. Несложен, прост в работе;

2. Надежен, труден для дешифровки посторонним;

3. Скрытен, по возможности не должен вызывать подозрений.

Шифры Бэкона сочетание шифрованного текста с дезинформа­цией в виде нулей. Двузначные коды и шифры использовались задолго до появления ЭВМ.

Кодирование имеет значение не только в конспиративных целях для шифровки информации. Так, в математике с помощью кодирования изу­чение одних объектов заменяют изучением других, более доступных или уже известных. Ярким примером кодирования в математике является метод координат, введенный Декартом, который дает возможность изучать гео­метрические объекты через их аналитическое выражение в виде чисел, букв и их комбинаций формул.

Теория кодирования довольно молодая наука. Исследование надежности кодов получило новый импульс после со­здания в 1948 г. Клодом Эльвудом Шенноном теории информации.

В основе теории информации лежит гипотеза о статистическом ха­рактере источника сообщений. Случайная последовательность знаков не несет информации, так же как и ключ кода. А расшифровать код Можно, используя знания о статистических закономерностях сообще­ния и кода. Теория количества информации Шеннона основана на из­вестной со времен Аристотеля альтернативе выбора одного из двух зна­ков между 0 и 1.

С появлением управляющих систем, в частности ЭВМ, роль кодирования существенно возросла и изменилась, так как без кодирования невозможна передача информации. В последнее вре­мя в связи с развитием телекоммуникационных систем и широ­ким использованием вычислительной техники для обработки и хранения информации возникла новая область знаний инфор­мационная безопасность.

Доступность проникновения через Интернет в экономиче­ские, политические, военные системы любой страны выявила новую мировую проблему борьбу с компьютерными взлом­щиками, хакерами, и компьютерными террористами.

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

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

Криптоаналитики пользуются мате­матическими методами при работе с информацией. Так, методы декодирования включают в себя решение различных уравнений. Разгадывание занимательных заданий, арифметических ребусов, в которых одинаковые цифры заменены одинаковыми буквами, а разные разными, связано с решением уравнений со многими неизвестными и основано на разложении числа по степеням ос­нования q.

2. Системы счисления для представления информации в ЭВМ

Проза в стихах Ей было тысяча сто лет, она в сто первый класс ходила. В портфеле по сто книг носила. Все это правда, а не бред. Когда, пыля десятком ног, она шагала по дороге, за ней всегда бежал щенок. С одним хвостом, зато стоногий. Она ловила каждый звук своими десятью ушами, И десять загорелых рук портфель и поводок держали. И десять темно-синих глаз Рассматривали мир привычно Но станет все совсем обычно, Когда поймете мой рассказ. А.Н. Старикова?

Система счисления - совокупность приемов наименования и записи чисел.

Система  счисления – совокупность различных знаков и правил, для записи чисел

Цифра – знак, предназначенный для записи чисел.

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

В современном мире наиболее распространенным является представление чисел посредством арабских цифр 0, 1,2, 3, 4, 5, 6, 7, 8, 9 специальных знаков, используемых для записи чисел.

Системы счисления различаются выбором базисных чисел, которые обозначаются знаками – цифрами и правилами образования из них остальных чисел

Системы счисления подразделяются:

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

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

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

Унарная система – это система счисления, в которой для записи чисел используется только один знак 1 .Следующее число получается из предыдущего добавлением новой 1; их количество (сумма) равно самому числу.

2.1. Позиционные системы счисления

Для изображения (представления) чисел используются в основном позиционные системы счисления. Привычной для всех является десятичная система счисления. В этой системе для записи любых чисел используется только десять разных знаков (цифр):

0, 1, 2, 3, 4, 5, 6, 7, 8, 9.

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

Рассмотрим число, записанное в десятичной системе:  343,32. В его записи   цифра 3 повторена три раза, при этом:

- левая цифра 3 означает количество сотен (ее вес равен 102);

- цифра 3, стоящая перед точкой, означает количество единиц (ее вес 10°),

- самая правая цифра 3 означает  количество десятых долей единицы (ее вес равен 10-1).

Последовательность цифр 343.32 представляет собой сокращенную запись выражения:

3·102 + 4·l01 + 3·100 + 3·10-1 + 2·10-2

Десятичная запись любого числа X в виде последовательности цифр имеет общий вид:

A=anqn + anqn-1 + an-2qn-2 + …+ a1q1 + anq0

или другая форма:

A=anqn-1 + an-1qn-2 + an-2qn-3 + …+ a2q1 + a1q0,

где: a0, a1, a2,…, an – цифры, q –основание системы счисления.

Запись числа в таком виде представляет собой полином, где каждый коэффициент ai ,- цифра и i=0,1,2,…n.

Про общий вид числа можно сказать, что некоторое число представлено в виде суммы степенней  основания системы счисления или оно разложено по степеням системы счисления.

Краткая запись числа в виде полинома представляет собой перечисление всех коэффициентов этого полинома.

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

Число единиц какого-либо разряда, объединяемых в единицу очередного старшего разряда, называют основанием позиционной системы счисления, а сама система счисления называется  q ричной.

Например, основанием десятичной системы счисления является число 10; двоичной число 2; троичной число 3 и т.д.

Для записи произвольного числа в q-ричной системе счисления достаточно иметь q разных цифр at, i=1,2,,q. Так, в троичной системе счисления любое число, может быть выражено посредством цифр 0, 1, 2. Эти цифры служат для обозначения некоторых различных целых чисел, называемых базисными.

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

Для установления факта, что число записано не в десятичной системе, около этого числа пишется нижний индекс, указывающий основание системы счисления:  35.548 или 101(2).

2.2.Перевод записи  числа из иной системы счисления в десятичную систему

Число раскладывается  по степеням основания системы счисления, в которой оно записано и находится значение получившегося полинома (числового выражения). Полученный результат есть число, записанное в десятичной системе счисления.

Задание 8-35.  Записать число в десятичной системе счислении:

а).    12345 = 1·53+2·52+3·5+4=1·125+2·25+3·5+4=194

б).   1011012=1·25+1·23+1·22+1=32+8+4+1=45

в).   332,415=3·52+3·51+2·50+4·5-1+1·5-2=3·25+3·5+2·1+4·0,2+1·0,04=92,84

2.3. Перевод записи целого числа из десятичной системы счисления в иную систему

Правило перевода основано на последовательном  деление с остатком. на число q- основание  системы.

  1. Данное число делится на q и находится первый остаток и первое частное.
  2. Если первое частное больше или равно q, то это частное  делится  на q, находятся второй остаток и второе частное.
  3. Если второе частное больше или равно q, то оно  делятся на q.
  4. Процесс деления и сравнения очередного частного с q продолжается до тех пор, пока  последующее частное не станет меньше q. Если где-то произошло деление на цело, то остаток считается равным нулю.
  5. Выписав последнее частное, затем, приписав к нему остатки в обратном порядке по отношению к их появлению, с учетом нулевых остатков, получается число, записанное в системе счисления с основанием q.

Задание 8-36. Перевести число 243 в пятеричную систему, q=5.

243:5 = 48(ост.3), 48>5

48:5 = 9(ост.4),   9>5

9:5 = 1(ост.4),    1<5.   Процесс деления окончен.

Ответ: 14435 – искомая  запись числа.

2.4. Перевод десятичной дроби в дробь с иным основанием.

Целая часть дроби переводится по правилу перевода целых чисел. Перевод дробной части основан на последовательном умножении на основание иной системы q:

1. Дробная часть десятичной дроби умножается на q. Целая часть получившегося первого произведения есть первая цифра, которая следует  после целой части числа в новой записи числа (первая цифра справа  от  знака, отделяющего целую часть этого числа от его дробной части).

2. Если дробная часть первого произведения не равна нулю, она  умножается на q. Целая часть получившегося второго произведения есть вторая цифра, которая следует после целой части числа в новой записи числа (вторая цифра справа  от  знака, отделяющего целую часть этого числа от его дробной части).

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

4.Выписывается целая часть новой  записи числа. К ней последовательно приписываются, в порядке появления цифры дробной части.

Задание 8-37.

а). Перевести десятичную дробь 0,234 в пятеричную систему счисления, q =5.

0,234·5= 1,17  –  первая цифра 1.

0,17·5  = 0,85  –  вторая цифра  0,

0,85·5  = 4,25  –  третья цифра  4,

0,25·5  = 1,25  –  четвертая цифра 1  и т.д.       Ответ: 0,10415 – искомая запись числа.

б). Проверить равенства: 0,2=0,00112 0,4=0,10123

Задание 8-38. Записать числа в десятичной системе счисления:

2456,      13729,      110012,       110013,      1011102

Ответ.

2456=2·36+4·6+5=101

1379, =9+3·9+7=43

110012 = 25

110013 =109

1011102 = 96

Задание 8-39. Составить систему счисления с основанием q=16.

q=10 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
q=16 0 1 2 3 4 5 6 7 8 9 A B C D E F
q=16 0 1 2 3 4 5 6 7 8 9 α β γ δ ε λ

Решение. Числа (цифры) от 0 до 9 берутся из десятичной системы счисления. Для чисел от 10 до 15 вводятся  специальные знаки или буквы латинского, греческого или иного  алфавита, которые при записи чисел, считаются цифрами в системе q=16. Один из вариантов цифр шестнадцатеричной системы  предложен в таблице.

Задание 8-40. Записать числа:  2 в двоичной системе счислении, 3 – в троичной системе , 4 – в четверичной системе. Число  k  в системе с основанием k . Установить закономерность в записи таких чисел.     Ответ: 10 во всех системах счисления.

Задание 8-41. Записать числа:

а).     1, 2, 4, 8, 16,… в двоичной системе;

б).     1, 3, 27, 81, …  в троичной системе;

в).     1, 5, 25, 125, … в пятеричной системе

Установить закономерность в записи таких чисел

Ответ с комментариями. Не трудно заметить, что числа в задании есть степени основания системы, поэтому все числа изображаются единицей с последующими нулями, число которых равно показателю степени. Например: 16=24=100002, 27=33=10003, kn =100…0 – k нулей

Задание 8-42 Найти значения х, при которых данные равенства будут верные .

а).      1001x=28,

б).      201x=33,

в).      302х+283х=140,

г).      1001х:11х=21х

д).      211х – 100х =17

е).      31х·32х=130

ж).      31х:13х=2

Ответы с решением.

а).     1·x3+1=28, x3=27.  При x=3.

б).     2·x2+1=33, x2=16, х=±4. При х=4

в).     3х2+2+2х2+8х+3=140, 5х2+8х-135=0.  Нет

г).     (х3 +1):(x+1) =2x +1. При х=3

д).     2х2+х+1 х2=17, х2+х – 16=0. Нет

е).     (3х+1)·(3х+2)=130, 9х2+9х-128=0. Нет

ж).     (3х+1):(х+3)=2, 3х+1=2(х+3). При  х=5


Задание 8-43. Перевести записи чисел в заданную систему.

а).      691=Х8

б).      1499 =Х12

в).      19510=Х12

г).      2134 =Х5

д).      173=Х2

е).      500782

ж).    0,6875=Х2


Ответ

а).      691=12638

б).      1499=А4B12

в).      19510 =B35A12

г).      2134=320145

д).      173=10110102

е).      50078=1010000001112

ж).    0,6875=0, 10112

а)
q=10 q=5 q=6 q=7 q=8 q=9
162 ***
586 ***
1121 ***
1762 ***
2257 ***
2340 ***
3704 ***
б)
q=10 q=2 q=4 q=5 q=8
93,72 ***
*** 0,1341
*** 0,60203
*** 1111,101
*** 11010,01011
34,056 ***
*** 234,02132
в)
q=10 q=3 q=6 q=7 q=8
*** 500,04
213,1426 ***
219,4219 ***
*** 555,55
*** 0,555
*** 2101,111
*** 0,342
а). Ответ
q=10 q=5 q=6 q=7 q=8 q=9
162 321
586 4321
1121 5065
1762 5065
2257 4321
2340 4444
3613 5065
3704 5065
в) Ответ
q=10 q=2 q=4 q=5 q=8
93,72 333,33
0,354 0,1341
0,754 0,60203
15,625 1111,101
26,354 11010,01011
34,056 40,00321
158,034 234,02132

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

в). Ответ
q=10 q=3 q=6 q=7 q=8
180,1111 500,04
213,1426 325,111
219,4219 333,33
365,7081 555,55
0,71891 0,555
0,19243 0,123
64,48148 2101,111
0,441406 0,342

2.5.   Арифметические действия над числами, представленными в различных системах счисления.

Как было сказано выше, правила выполнения арифметических действий над  числами, записанными в любой системе счисления, не отличаются от правил, которые применяются при выполнении таковых действий в десятичной системе счисления.

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

Составим таблицы сложения и умножения для пятеричной системы счисления, q=5.

Таблица сложения, q=5 Таблица умножения  q=5
0 1 2 3 4 0 1 2 3 4
0 0 1 2 3 4 0 0 0 0 0 0
1 1 2 3 4 10 1 0 1 2 3 4
2 2 3 4 10 11 2 0 2 4 11 13
3 3 4 10 11 12 3 0 3 11 14 22
4 4 10 11 12 13 4 0 4 13 22 31

Находим по таблице сложения: 4 +3=12. Число единиц 2 пишется  под единицами первого разряда, число 1 (единицы второго разряда) запоминается.

3+4=12, 12+1=13,  3 пишется под единицами второго разряда, 1 запоминается. 2+1=3, 3+1=4, 4 пишется  под единицами третьего разряда. Ответ: 4325

Находим по таблице умножения 4·3=22, число единиц 2 пишется  под единицами первого разряда второе число 2 (единицы второго разряда) запоминаются. 3·3=14, 14+2=21, 1 запишем под единицами второго разряда, 2 запоминается. 3·2=11, 11+2=13, 13 пишем под единицами 3 и 4 разрядов. Получили первое не полное произведение 13125.

Аналогично находится второе неполное произведение 2345·45=21105 – единицы второго разряда или получилось число 211005. Складываются оба неполные произведения.  Ответ 223225

Таблицы сложения и умножения позволяют выполнять соответственно вычитание и деление чисел.

1. Выполнение арифметических действий без таблиц сложения и  умножения.

Данный способ предполагает  устные вычисления по переводу двузначных чисел из одной системы счисления в другую.

410+310=710, это 125, число 2 пишется под первым разрядом, число 1 запоминается.

310+410=710, 710+1=810, это 135число 3 пишется под вторым разрядом, число 1 запоминается.

210+110=310, 310+1=410, это 45, пишется под третьим разрядом.

Теоретическое обоснование данного приема не составляет трудности, оставляем выполнить его самостоятельно. Аналогично можно выполнять остальные арифметические действия.

3. Использования посредника.

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

Задание 8-45.

1. Выполнить действия в указанных системах счисления:

а), 23426-5556 б). 2457*237 в). 42315-4445 г). 349*24

д). 23578:268 е). 1000:101                  ж).10013:113

Ответы: а-1343, б – 6331, в- 3232, г- 14112, д- 66, е-11(ост.1), ж-21

2. Переведите в двоичную, восьмеричную и шестнадцатеричную системы счисления числа:  53;  62;  71;  84;  96;  47.

3. Переведите двоичное число в десятичную, восьмеричную и шестнадцатеричную системы счисления:

а) 010011;   б) 100111;   в) 110100;   г) 010101;   д) 101010;   е) 010010.

4. Найдите сумму, разность и произведение чисел А и В в двоичной системе счисления и сделайте проверку результата в десятичной системе счисления:

а). А= 100110,      б).А = 010111,     в). А = 0110И,    г). А= 101100,

В=001001;           В=101000;               В = 010010;        В=101000;

5. Выполните сложение и вычитание в шестнадцатеричной системе счисления и сделайте проверку в десятичной:

а).  C3896 и 845FA.                б).  В4599 и A74F5.              в). F79832 и С9А53.

г) 987F4и 5ADF7;                   д).  D5B6C и B7AF8..          е)  87FDC и 5АВ63;

2.6. Смешанные системы счисления.

Это необычные  системы счисления, когда в записи числа используется 2, и более оснований q1, q2, …q n.  Основаниями  должны быть простыми различными числами Идея таковых системах заключается в том, что с одним основанием, изображаются с помощью цифр другой системы счисления.

Пусть некоторое число записано в системе с основанием q, тогда каждое число, соответствующее каждой цифре записи числа, представляется в новой системе счисления p. Очевидно первичное (старшее) основание q больше вторичного (младшего) основания p, а именно p<q.. Такая система называется  p-q ричной системой. В конкретных случаях: двоично-троичная система (2-3я система), двоично-десятичная система (2-10я система)  и  др.

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

Правило записи чисел в смешанной системе счисления

1. Все цифры системы с  первичным основанием (вернее числа им соответствующие), записываются с помощью цифр вторичного основания.

2. Устанавливается максимальное число разрядов в таковых записях и путем добавления слева нулей, число разрядов в каждой записи выравнивается.

3. Все цифры в первоначальной записи числа, заменяются наборами цифр,  им соответствующим записям вторичного основания.

4. Если в начале записи числа окажутся нули (слева от старшего разряда),  и то их надо отбросить. При записи чисел, имеющих дробную часть, то нули крайние справа также отбрасываются.

Задание 8-46. Составить таблицу перевода записи чисел из десятичной системы счисления в троично-десятичную систему.

Записать в ней числа 2345;  129;    506003;   23,45.

Решение:

1. Составим таблицу записи чисел в троично-десятеричной  системе.

q=10 0 1 2 3 4 5 6 7 8 9
q=3 0 1 2 10 11 12 20 21 22 100

2. Наибольшее число разрядов равно трем, поэтому таблица перевода чисел примет окончательный вид:

q=10 0 1 2 3 4 5 6 7 8 9
q=3 000 001 002 010 011 012 020 021 022 100

2. Запишем числа:

2345=002 010 011 0122-10 , отбросив первые два нуля, получим: окончательную запись  2 010 011 0122-10

129=001 002 1002-10 = 1 002 1002-10 506030=12 000 020 000 010 0002-10

23,785=002 010, 011 021 022 012

Задание 8-47. Составить таблицу перевода записи чисел из десятичной системы счисления в двоично-десятичную систему. Записать в ней числа 925; 1046; 15,4

Ответ

q=10 0 1 2 3 4 5 6 7 8 9
q=2 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001

925 = 1001 0010 01012-10;        1046 =1 0000 0100 01102-10

15,8= 1 0101,12-10

Задание 8-48. Используя знания, полученные при выполнении заданий 9-10, перевести числа  из одной системы счисления в другую

а).  10021000122-1010

б).  21012000020 2-1010

в).  1001 1000 0011 2-1010

г).  11100100110 2-10= Х10

Ответ:   а 001 002 100 0122-10= 1295;     б 021 012 000 020 2-10= 7506 10

в- 1001 1000 0011 2-10= 98310 г 0111 0010 0110 2-10= 72610

Введем некоторые уточнения связанные с позиционными системами счисления.

1.  Вес разряда – отношение pi= qi / q0 = qi, где i – номер разряда, считая справа. Так, в  числе 12345 вес первого разряда равен 10 второго – 100 и т.д.

2.  Длина числа количество разрядов в разложении данного числа по разрядам

2.7. Двоичная система счисления. Для представления информации в ЭВМ используется двоичная система счисления или, как говорят, применяется двоичное кодирование. Основание двоичной системы q = 2, алфавит ее состоит, соответственно, из двух цифр: 0 и 1. Двоичное кодирование или двоичный  код имеет ряд достоинств, например:

~ простота в обращении, так как использует всего два символа 0 и 1;

~  соответствие этих символов техническим характеристикам цифровых схем, также имеющих два устойчивых состояния: рабо­чее (1) и нерабочее (0).

Многие явления природы и техники описываются также двумя состояниями: есть нет, включен выключен, проходит (ток, сиг­нал)  не проходит и др.

Символы 0 и 1 позволяют кодировать логических понятий истина (1) и ложь (0).

В двоичной системе, как и в любой другой ПСС, каждый раз­ряд имеет определенный вес, а именно 2k для любого k e 2.

Вес первых двенадцати разрядов
q1=10 2048 1024 512 256 128 64 32 16 8 4 2 1
q2 = 2 211 210 29 28 27 2б 25 24 23 23 21

Вес первых 12 разрядов цифр двоичного числа можно предста­вить в виде таблицы.

В двоичной записи каждый разряд несет свою единицу инфор­мации и называется битом[1].

Самый младший двоичный разряд называется наименьшим, а са­мый старший  наибольшим значащим битом. Каждый из них имеет соответственно наименьший и наибольший вес. В двоичной запи­си числа это соответственно крайний слева и крайний справа биты. Для измерения большого количества информации используется еще одна единица измерения: 8 бит образуют 1 байт.

Несмотря на преимущества двоичной системы счис­ления, ее недостаток  громоздкая форма записи двоичного слова. Поэтому в ЭВМ нашли применение и другие системы счисления.

Шестнадцатеричная система счислении, система счисления с основанием q -  16 (16 = 24) дает самую компактную запись числа в ЭВМ. Для перевода двоичного числа в эту систему разбивают двоичную запись на четверки (тетры) и заменяют их соответству­ющим эквивалентом в шестнадцатеричной системе, пользуясь таблицей перевода.

Задание 8-49.

q=10 q=2 q=8 q=16
9 1001 11 9
10 1010 12 А
11 1011 13 В
12 1100 14 С
13 1101 15 D
14 1110 16 Е
15 1111 17 F
16 10000 20 10
17 10001 21 11
q=10 q=2 q=8 q=16
0 0000 00 0
1 0001 01 1
2 0010 02 2
3 ООП 03 3
4 0100 04 4
5 0101 05 5
6 0110 06 6
7 0111 07 7
8 1000 10 8

1. Перевести F516 в двоичную систему счисления.

Решение. Представим F516 как F16 и 516. По таблице находим: FJ6 = 11112 и  516 = 01012,

Ответ. F516=  111101012

2. Перевести чис­ло 100011102 в шестнадцатеричную систему счисления.

Решение. Представим 100011102 как 10002 и 11102 Имеем 10002 = 81 6, 11102 = Е16.

Ответ. 8E16

При чтении чисел в иных, не десятичных, системах счисления принято называть отдельно каждую цифру. Сравним: 2510 -  это двадцать пять, но 258 читается как два пять. В ЭВМ самостоя­тельно осуществляется перевод чисел из одной системы счисле­ния в другую.

Проблема отношения между основанием системы счисления (мощно­стью алфавита) и длиной получившегося слова связана  с законом обратной зависимости объема и содержания. Обратим внимание на следствие этого в лингвистике. В после­днее время встала проблема поиска оптимального алфавита, обо­стрившаяся в связи с попытками перевести письменность неко­торых народов с кириллицы (33 литеры) на латинский алфавит (26 знаков). Считается, что 32 33 знака являются опти­мальным объемом алфавита и для запоминания, и для написа­ния и произношения слов. По этой же причине, системы счисле­ния с основанием q = 10 – 16, являются оптимальными. Деся­тичная  наиболее употребляемой из них.

2- 8. Связь между системами счисления с основаниями q=2n.

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

Двоичная система счисления имеет две  цифры: 0 и 1.

Восьмеричная система счисления имеет  восемь   цифр 0, 1, .,7.

Шестнадцатеричная система счисления имеет 16 цифр. Как было отмечено раннее, цифры  0, 1, , 9 – взяты из десятичной системы, а для обозначения чисел  10, 11, 13,14, 15 используются соответственно  буквы латинского алфавита:  А;  В; С; D; Е; F.. Виду этого можно записать: А16=1010; Б16=1110; C16=1210, D16=1310; Е16=1410; F16=1510. Связь представления чисел в системах счисления с основаниями q=10, q=2. q- 8, q=16 показано в таблице.

Перевод чисел из одной из систем  в другую осуществляется по правилам,  построенным на основе теорем, которые доказываются в теоретической части информатики.

Перевод записи числа из двоичной системы счисления в восьмеричную систему. Учитывая, что 8=23 число, записанное в двоичной системе счисления, разбивается  справа налево на группы по три знака (3-  показатель степени) в каждой  из них. Каждая группа отдельно переводится  в восьмеричную систему счисления с учетом  не значащих нулей.

q=10 q=2 q=8 q=16
0 0 0 0
1 1 1 1
2 10 2 2
3 11 3 3
4 100 4 4
5 101 5 5
6 110 6 6
7 111 7 7
8 1000 10 8
9 1001 11 9
10 1010 12 А
11 1011 13 В
12 1100 14 С
13 1101 15 D
14 1110 16 Е
15 1111 17 F

Задание 8-50. Перевести число Х их двоичной системы в восьмеричную систему. Х= 10101101110012

Решение: Х= 1 010 110  111  1012. Группе  1 соответствуют цифра 1.  Группе  010 – цифра 2.  Группе 111-  цифра 7. Группе          101 – цифра 5

Ответ: 10101101110012 = 12758

Перевод записи числа из двоичной системы счисления в шестнадцатеричную систему. Учитывая, что 16=24 число, записанное в двоичной системе счисления, разбивается  справа налево на группы по четыре знака (4-  показатель степени) в каждой  из них. Каждая группа отдельно переводится  в восьмеричную систему счисления с учетом  не значащих нулей.

Задание 8- 51. Перевести число Х их двоичной системы в шестнадцатеричную систему. Х= 10101101111112

Решение: Х= 1  0101  1011  11112. Группе  1 соответствуют цифра 1.  Группе  0101 – цифра 5.  Группе 1011-  цифра В. Группе 1001 – цифра F.  Ответ 10101101111112=15BF

Перевод записи числа из восьмеричной или шестнадцатеричной системы счисления в двоичную систему.

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

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

Задание 8- 52. Перевести числа из одной системы счисления в другую

а). 234582

Решение:  Цифре 2 соответствует набор знаков: 10 добавляем его до трех знаков 010. Цифре 3 – набор 11, или 011. Цифре 4 – набор 100. Цифре 5  набор 101. 23458 = 010 011 100 1012.  Ответ: 10 011 100 1012

б). D4A38162

Решение:  D  1101                4  0100         A-  1010         3-  0011          8  1000

Ответ:  D4A3816 = 1101 0100 1010 0011 10002

Задание 8- 53. Проверьте правильность  представления чисел

D316 = 1101 00112

10 10012 = 2916 = 258

Правила взаимного перевода чисел в рамках двоичной, восьмеричной и шестнадцатеричной систем  распространяются на перевод чисел в рамках систем, основания которых находятся в зависимости:  q,  p1 = qn , p2 = qk …, где n и k – натуральные числа.

Задание 8- 54. Составить таблицу перевода чисел в рамках троичной, девятеричной,  двадцатеричной систем счисления.

3. Основные понятия вероятностной теории информации

Сигнал есть сообщение, передаваемое с помощью некоторого носителя. Если источник вырабатывает сигнал, параметр которо­го является непрерывной функцией времени, то он называется непрерывным. Непрерывна и информация, передаваемая такими сигналами.

Сигнал называется дискретным, если соответствующие ему числовые значения существуют в конечный момент времени и представляют собой конечную последовательность символов, на­пример 0 и 1.

В дискретных сообщениях, конечных или бесконечных после­довательностях знаков, можно проводить разбиения на конечные последовательности знаков  слова.

Пусть дано некоторое множество знаков М. Говорят, что зада­но слово над множеством М, если оно составлено из элементов множества М.

Для множества двоичных символов В={0,1} двоич­ным словом длины п будет последовательность знаков, содержа­щая k нулей и i единиц, причем k + i = п. Например, кортеж 010111 есть слово длины 6 над B, двоичный код некоторого чис­ла, содержащий k = 2 нулей и i = 4 единиц. Длина двоичного слова может быть неограниченной.

Процедура преобразования непрерывных сигналов в дискрет­ные, называется дискретизацией. Для ее проведения выбирают из алфавита конкретные символы, которые характеризуют все цело­стное сообщение.

К анализу информации возможны различные подходы.

Объемный подход связан с подсчетом количества информации в двоичной системе счисления с учетом количества символов.

Вероятностный подход учитывает частоту появления символа в тексте.

Однако при таких подходах упускается истинность (семанти­ческая характеристика), а также полнота, актуальность, ценность текста.

К свойствам информации можно отнести:

~   запоминаемость (возможность сохранения);

~   передаваемостъ без искажений, с помощью различных кана­лов связи;

~  воспроизводимость;

~  преобразуемое, т.е. представление информации в разной форме, в том числе ее копирование;

~  стираемость  преобразование, при котором количество ин­формации в новой форме уменьшается до нуля.

3.1.Измерение информации. Математическое представление об ин­формации связано с ее измерением. Существует несколько подхо­дов к измерению количества информации.

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

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

Мерой беспорядка любой системы является энтропия. Понятие энтропии как меры беспорядка системы заимствовано из термо­динамики и стало одним из основных не только в теории инфор­мации, но и в современном философском осмыслении открытых биосоциальных систем.

В замкнутых системах любые процессы протекают так, чтобы энтропия системы не убывала.

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

3.2.Формула Хартли. Итак, в передачу сообщения входит процесс выбора, который осуществляет как отправитель, так и получа­тель сообщения. Этот процесс выбора можно измерить количе­ственно.

Пусть нам необходимо передать одно из восьми возможных сообщений: А, В, С, D, E, F, /, Н. Условимся для удобства поста­вить в соответствие каждому сообщению двоичное число и пред­ставим результат в виде графа, где каждому сообщению соответствует свой набор сигналов.

~       Один двоичный сигнал позволяет выбрать одно из двух сообщений: 2 = 2.

~       Два двоичных сигнала позволяют выбрать одно из четырех сообщений: 4 = 22.

~       Набор из трех сигналов  одно из восьми сообщений: 8 = 23,

~       Набор из шести  одно из шестидесяти четы­рех сообщений: 64 =  2б,

~       Набор из т двоичных сигналов  одно из 2т сообщений.

Наоборот, для набора N= 2m сообщений нужно иметь не менее т сигналов. Важно знать, что одно из тридцати двух сообщений выбирается с помощью пяти сигналов. Поэтому для распознавания одного определенного сообщения из N возможных сообщений требуется т = log2N сигналов.

При N = 100 требуется т = Iog2100 = Iog2l02 = 2Iog210 = = 2 • 3,32 = 6,64 = 7 знаков. Следовательно, для выбора одного из N вариантов нужна информация в J бит: J= log2N.

Двоичное дерево будет иметь вид:

n=1.  2 сообщения                   0          1

n=2.  4  сообщения                 00        01        10        11

n=3.  8 сообщений                  000      001      010      011      100      101      110      111

n=4.  16 сообщений                0000                                                           .                1111

Процесс составления дерева можно продолжить  любого n.  Алгоритм составления дерева похож на правило нумерации набором аргументов для составления таблицы истинности логических формул.

Представленное дерево позволяет закодировать первые 8 букв, например латинского алфавита:    А, В, С, D, E, F, /, Н при n=3.

Если N = 100, то  требуется т = Iog2100 = Iog2l02 = 2Iog210 = = 2 • 3,32 = 6,64 7 знаков. Следовательно, для выбора одного из N вариантов нужна информация в /бит: J= Iog2N.

Эту формулу в 1928г. предложил американец Хартли. В качестве единицы измерения используется бит. Таким образом, для выбора из 8 знаков потребуется 3 бита.

Замечание. Формула Р. Хартли является частным случаем формулы Шеннона, которая рассматривает исходы с разной вероятностью. Для расчета количества информации в таких случаях суммируются произведения вероятностей на количество информации каждого сообщения. Соответствующая  формула имеет вид:

Не трудно установить, что указанная формула может рассматриваться как некоторая функция H, которая принимает свой максимум при равновозможных исходах. Это значит, что все n сообщения имеют одинаковую вероятность появления p=1/n. При этом формула примет вид:

.

Полученная формула есть ни что иное, как  формула Хартли.

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

Частный случай, это тот случай, когда рассматриваются  условия равновероят­ных исходов. Частную информацию, содержащуюся в сообщении Xi находитcя  по формуле:

Следствия формулы Хартли.

1. Если возмож­но передать только один сигнал (п = I), то Н = Iog2l = 0. Видим, что подобные сообщения не содержат информации вообще. На­пример, если каждое утро восходит солнце, то, вставши в любой день и увидев светящее солнце, мы ничего нового не узнаем.

2. Если с равной вероятностью могут передаваться два сигнала (п = 2), то Н= Iog22 = 1 бит. Это также понятно, поскольку форму­ла Хартли как раз и строилась в предположении о двоичности бита, и мы лишь проверили ее действие на себя и тем самым непротиворечивость. Так, не тикающие часы свидетельствуют нам о том, что они остановились, тикающие  что идут.

3. Если H1 энтропия до принятия сообщения и H2  энтропию после принятия сообще­ния?  то  J = H1 H2

Задание 8-55. Найти количество информации, имеющееся при получении сообщения на русском языке.

Решение. Так как в русском языке 33 буквы и 1 пробел между словами, то необходимо 34 места для символов. Тогда по формуле Хартли имеем J= Iog234 = 5,09 бит.

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

Анализ больших тек­стов дает такие численные значения статистической вероятности появления букв в тексте.

Если учитывать частоту появления каждой буквы в тексте, то по формуле Шеннона:

~       Н= 4,35 бит для русского текста, в котором не более 33 букв.

~       J = Iog2 27 = 4,76 бит  для латин­ского алфавита, в котором 26 букв.

Задание 8-56. На одной из клеток шахматной доски стоит фигура. Будем считать, что все положения этой фигуры на шахматной доске равновероятны.

1. Какое количество информации несет в себе сообщение о точ­ном месте нахождения этой фигуры?

Решение. Неопределенность информации (энтропия) этой системы А с N равновероятными состояниями по форму­ле Хартли равна:

log2N, J= Н(А) = Iog264 = Iog226 = 6 бит.

Ответ. Сообщение о том, что фигура находится на любой клетке, например, на клетке D5, несет в себе 6 бит информации.

2. Какое количество информации несет в себе сообщение о том, что фигура находится на одной из угловых клеток доски?

Решение. Так как на доске четыре угловых клетки, а вероят­ность находиться на каждой из них 1/64, то вероятность попасть на угол р = 4/64 = 1/16.

Частная информация сообщения равна

Задание 8-57. Какую частную информацию несет сообщение: В суб­боту я иду в гости?

Решение. В гости можно пойти в любую субботу года. Число суб­бот в году: 12 • 4 = 48 (фактически суббот в году больше, 365:7»52,14).

Вероятность пойти в гости в субботу Р = 1 /48.

Частная информация

Задание 8-58. Один человек сказал другому: На этой неделе мой день рождения.

1. Какое количество информации заключено в этом сообщении?

Решение. Так как любой из семи дней недели равновероятен, то Рi = 1/7. Тогда частная информация

2.  Каким минимальным числом уточняющих вопросов, подра­зумевающих ответы да и нет, можно узнать точный день рож­дения знакомого?

Решение. Информация, согласно предыдущего решения  заключена в сообщении JА » 2,8» 3 бит, то необходимо минимум три во­проса для выяснения точного дня рождения. Представим все дни недели на рисунке в виде отрезка с се­мью делениями  и воспользуемся правилом половинного деления

Пусть неизвестный день рождения в субботу, тогда вари­ант диалога будет таким.

Вопрос 1: Твой день рождения до четверга?

Ответ I: Нет.

Вопрос 2: Твой день рождения после пятницы?

Ответ 2: Да.

Вопрос 3: Твой день рождения в воскресенье?

Ответ 3: Нет.

Вывод: днем рождения знакомого будет суббота.

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

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

Любое выдающееся обществен­ное явление, значительное событие культуры, достижение со­временной техники по своей сути являются различными вида­ми передачи, переработки и хранения информации. Обработка разнообразной информации  основной смысл функциониро­вания ЭВМ.

Математическая теория информации появилась после того, как было установлено, что количеству информации можно поставить в соответствие число аналогично тому, как с помощью чисел выражаются различные физические величины: скорость, темпе­ратура, масса и др.

Принцип получения формулы для количества информации можно проиллюстрировать на примере игры, смысл которой заключается в том, что для установления некоторой ин­формации можно задавать уточняющие вопросы, на которые даются лишь два ответа: Да и Нет или на языке двузначной логики 1 и 0. Тогда последовательности вопросов будет соот­ветствовать серия ответов в виде кодового слова над множеством {0, 1}. Указанная игра часто  называется игрой Бар-Кохба[2]

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

Любое сообщение, подразумевающее выбор одной из двух аль­тернатив, содержит I бит информации. Так, 1 бит информации несет в себе ответ на любой уточняющий вопрос.

Обычно, в зависимости от характера информации, выбирается наиболее целесообразный способ ее кодирования.

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

Наше письмо  тоже способ кодирования. Звукам мы ставим в соответствие буквы некоторого алфавита. Тогда процесс деко­дирования есть чтение написанного текста. В таком случае уст­ройством, кодирующим и декодирующим озвученную информа­цию, является мозг человека, а каналом связи  написанный текст.

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

Люди, терпящие бедствие, передают сигнал SOS свистками на суше, а мореплаватели на судах  световыми сигналами.

Студия звукозаписи тоже осуществляет кодирование музыкаль­ных звуков и речи и их запись на магнитную кассету.

Компози­тор кодирует ту же музыку с помощью семи нот.

Задание 8-59. Приведите различные примеры кодирования и декодирования сигналов.

Задание 8-60. Сколько бит информации содержит номер одного (строго определенного, например моего) паспорта?

Решение. Так как в стране 145 миллионов россиян, то надо най­ти длину кодового слова, соответствующего одному из двух вари­антов, для того чтобы определить, мой это паспорт или нет. Тогда 2J= 145000000 или J= Iog2145000000, т.е. J= 27.

Формула Хартли J=log2 N позволяет установить важное свой­ство аддитивности информации для определения количества ин­формации, соответствующего двум сообщениям.

J1 + /2 = log2 N1 + log2N2 = log2(NiN2).

Знание формулы Хартли для подсчета количества информа­ции помогает решать различные задачи в одном из разделов тео­рии информации  теории поиска. Задачи этого раздела анало­гичны задачам поиска фальшивой монеты из некоторого множе­ства,

Задание 8-61. Пусть имеется 27 монет, среди  которых одна фальшивая монета. Найти ее путем взвешиваний. Установить возможное число таких взвешиваний.

Решение. Фаль­шивой может оказаться любая из имеющихся 27 монет, поэтому можно воспользоваться формулой Хартли. Минимальное коли­чество информации о фальшивой (тяжелой либо легкой) монете равно J= Iog227 = Iog233 = 31og23.

4. Понятие кодирования информации

Ты должен идти не той дорогой, какой идут другие,

но той, которой следует идти. Сенека

4.1. Основные понятия теории кодирования

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

Первая же задача коди­рование информации касается не только передачи, но и обра­ботки, и хранения информации, т.е. охватывает широкий круг про­блем; частным их решением будет представление информации в компьютере. С обсуждения этих вопросов и начнем освоение теории кодирования.

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

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

Кодирование предшествует передаче и хранению информации. При этом, как указывалось ранее, хранение связано с фиксацией некоторого состояния носителя информации, а передача с изме­нением состояния с течением времени (т.е. процессом). Эти состоя­ния или сигналы будем называть элементарными сигналами -именно их совокупность и составляет вторичный алфавит.

Первая теорема Шеннона: При отсутствии помех всегда возможен такой вариант кодиро­вания сообщения, при котором среднее число знаков кода, приходящихся на один знак первичного алфавита, будет сколь угодно близко к отношению средних информации на знак пер­вичного и вторичного алфавитов.

Используя понятие избыточности кода, можно построить иную формулировку теоремы Шеннона:

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

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

Пусть заданы два ал­фавита состоящие из конечного числа символов:

А = {а1, а2, , an} – первичный алфавит

В = {b1, b2, , bm}- вторичный алфавит

Словом называется любой кортеж из символов этих алфавитов. Слово называется  пустым словом, если оно не содержащим символы.  Такое слово обозначается символом Λ.

Длина  слова равна n количеству символов в слове.

Первая буква слова называется префиксом, последняя - постфиксом

Слова, как и кортежи можно соединять. Для этого префикс второго слова дол­жен следовать сразу за постфиксом первого, при этом в новом сло­ве они, естественно, утрачивают свой статус, если только одно из слов не было пустым.

Соединение слов а1 и а2 обозначается а1 а2. Соединение п одинаковых слов а обозначается аn, причем а° = Λ.

Множество всех непустых слов алфавита A будем обозначать символом  A*. Множество слов, состав­ленных в алфавите B, обозначим B*.

Множество A часто называют алфавитом сообщений,  множество В кодирующим алфавитом.

Обозначим через F отображение слов алфавита А в алфавит В. Тогда слово р = F(a) назовем кодом слова а (от лат. codex).

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

Код правило, описывающее соответствие знаков или их сочетаний первичного алфавита знакам или их сочетаниям вторичного алфавита.

Код набор знаков вторичного алфавита, используемый для представления знаков или их сочетаний первичного алфа­вита

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

Процесс преобразования слов исходного алфавита A в алфавит B называется кодиро­ванием информации. В символьном виде запишем F: A*®B*

Кодирование - перевод информации, представленной сооб­щением в первичном алфавите, в последовательность кодов.

Процесс обратного преобразования слова называется декодированием. Декодирование можно рассматривать как функцию F-1 – обратную функции F – кодированию.

Декодирование - операция, обратная кодированию, т.е. восстановление информации в первичном алфавите по по­лученной последовательности кодов.

Кодер - устройство, обеспечивающее выполнение операции кодирования.

Декодер - устройство, производящее декодирование.

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

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

Правила обработки могут быть различными:

~       поэлементное кодирование,

~       кодирование с помощью алгоритма,

~       кодиро­вание с помощью различных видов графики и др.

Так как для любого кодирования должна вы­полняться операция декодирования, то отображение должно быть обратимым (биекция).

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

Абстрактным алфавитом является  упорядоченное дискретное множество символов.

Например:

~     алфавит букв русского языка А, Б, В, , Я, мощность кото­рого n = 33;

~     алфавит арабских цифр 0, 1, 2, , 9, п = 10;

~    двоичный алфавит B = {0, 1}, n = 2;

~    двоичный алфавит {точка, тире}, n = 2;

~    алфавит римской системы счисления I, V, X, L, С, D, М;

~    алфавит языка блок- схем для изображения алгоритмов:

Особое  значение имеют алфавиты, содержащие два элемента  двоичный, или бинарный, набор символов. Например:

~      пара цифр {О, 1},

~      семантические значения ис­тина и ложь {и, л],

~      пара ответов {да, нет},

~      пара состояний включено и выключено,

~      знаки азбуки Морзе {· , } (точка, тире).

4.2. Алфавитное кодирование.

4.2.1. Не равномерное кодирование

Знаки первичного алфавита (например, русского) кодируются комбинациями символов двоичного алфавита. Это: 0 и 1.  Длина кодов и, соответственно, длительность передачи отдельного кода, могут различаться. Длительности элементарных сигналов при этом одинаковые.

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

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

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

00100010000111010101110000110

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

Первый состоит в использовании специальной комбинации элементарных сигналов, которая интерпретируется декодером как разделитель знаков. Его называют Неравномерный код с разделителем

Разделителем отдельных кодов букв может быть последовательность 00 (признак конца знака), а разделителем слов  000 (признак конца слова пробел). При этом можно установить правила построения кодов, например некоторые их таковых:

~     код признака конца знака может быть включен в код буквы, поскольку не существует отдельно (т.е. кода всех букв будут заканчиваться 00);

~     коды букв не должны содержать двух и более нулей подряд в середине (иначе они будут восприниматься как конец знака);

~     разделителю слов (000) всегда предшествует признак конца знака и др.

Неравномерный код может быть однозначно декодирован, если никакой из кодов не совпадает с началом (префиксом) какого-либо иного более длинного кода.

Второй в применении префиксных кодов. В языковедении термин «префикс» означает «приставка». При прочтении (расшифровке) закодированного сообщения путем сопоставления с таблицей кодов всегда можно точно указать, где заканчивается один код и начинается другой.

Таблица претесных кодов некоторых

русских букв

а л м р у ы
10 010 00 11 0110 0111

В качестве примера рассмотрим таблицу префиксных кодов:

Пусть требуется декодировать сообщение: 00100010000111010101110000110, в котором  отсутствуют коды конца знака и слова.

Декодирование производится следующим образом:

1. Выписывается первый слева символ. Это 0. Сравнивается  с таблицей кодов. Совпадений нет. Выписывается второй символ. Это 0. Получили слова 00. Ему соответствует буква м

2..Выписывается третий  слева символ. Это 1. Сравнивается  с таблицей кодов. Совпадений нет. Выписывается четвертый символ. Это 0. Получили слова 10. Ему соответствует буква а

Процесс циклический и повторяется до тех пор, пока не расшифруется все слово. В примере зашифровано текст Мама мыла раму

00  10  00  10                          – мама

00   0111  010  10                    –мыла

11  10  00  0110 раму

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

4.2.2. Равномерное алфавитное двоичное кодирование. Байтовый код

Двоичный код первичного алфавита строится цепочками равной длины. Формировать признак конца знака не требуется. Приемное устройство  отсчитывает оговоренное заранее количество элементарных сигналов и интерпретирует цепочку, соотнося ее с таблицей кодов. При этом недопустимы сбои, например, пропуск одного элементарного сигнала приведет к сдвигу всей кодовой последовательности и неправильной ее интерпретации; решается проблема путем синхронизации передачи или иными способами.

С другой стороны, применение равномерного кода оказывается одним из средств контроля правильности передачи, поскольку факт поступления лишнего элементарного сигнала или, наоборот, поступление неполного кода сразу интерпретируется как ошибка.

Число знаков (сигналов) равномерного кода определяется по формуле:

k ≥ Log2 N,  где k-число сигналов, N число символов в алфавите

Примером равномерного алфавитного кодирования является телеграфный код Бодо, пришедший на смену азбуке Морзе. Ис­ходный алфавит должен содержать не более 32-х символов.

k= Log2 32 = 5.

Каждый знак первичного алфавита содержит 5 бит информации и кодируется цепочкой из 5 двоичных знаков.

В русском алфавите 34 буквы (с пробелом). Поэтому пришлось объединить в один знак буквы е ё,  ь ъ,. После такого сжатия N = 32. Знак препинания, либо отсутствуют, либо заменяются буквенными аббревиатурами; такими как ТЧК, ЗПТ и др.

Равномерное алфавитное кодирование используется при представлении символьной (знаковой) информации в компьютере. Чтобы определить длину кода, необходимо начать с установления количество знаков в первичном алфавите. Компьютерный алфавит должен включать:

1.  Прописные и строчные буквы латинского алфавита, всего 26 х 2 = 52шт.

2.  Прописные и строчные буквы русского алфавита:33 х 2 = 66шт.

3.  Цифры от  0 до .9 всего 10шт.

4.  Знаки математических операций, знаки препинания, специальные символы, всего  20шт.

Общее число символов N= 148.

Длина кодовой цепочки: k > Log2148 > 7,21. Длина кода выражается целым числом, поэтому берется k = 8.

Такой способ кодирования принят в компьютерных системах: любому символу ставится в соответствие код из 8 двоичных разрядов (8 бит). Эта последовательность сохраняется и обрабатывается как единое целое (т.е. отсутствует доступ к отдельному биту) по этой причине разрядность устройств компьютера, предназначенных для хранения или обработки информации, кратна 8. Совокупность восьми связанных бит получила название байт, а представление указанным образом символов байтовым кодированием.

Байт наряду с битом может использоваться как единица измерения количества информации в сообщении.

1байт соответствует количеству информации в одном знаке алфавита при их равновероятном распределении.

Этот способ измерения количества информации называется объемным.

Байт принят в качестве единицы количества информации в международной системе единиц СИ.

1 байт = 8 бит.

1 Кбайт = 210 байт = 1024 байт        -   килобайт

1 Мбайт = 220 байт = 1024 Кбайт      -   мегабайт

1 Гбайт = 230 байт = 1024 Мбайт                  -   гигабайт

1 Тбайт = 240 байт = 1024 Гбайт                   -   терабайт

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

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

Первым таким международным стандартом, который применялся на больших вычислительных машинах, был EBCDIC (Extended Binary Coded Decimal Interchange Code) расширенная двоичная кодировка десятичного кода обмена.

В персональных компьютерах и телекоммуникационных системах применяется международный байтовый код ASCII (American Standard Code for Information Interchange стандартный американский код обмена информацией).

Он регламентирует коды первой половины кодовой таблицы (номера кодов от 0 до 127, т.е. первый бит всех кодов 0). В эту часть попадают коды прописных и строчных английских букв, цифры, знаки препинания и математических операций. Сюда же попали и некоторые управляющие коды (номера от 0 до 31), вырабатываемые при использовании клавиатуры.

Вторая часть кодовой таблицы она считается расширением основной охватывает коды в интервале от 128 до 255 (первый бит всех кодов 1). Она используется для представления символов национальных алфавитов (например, русского), а также символов псевдографики. Для этой части также имеются стандарты, например, для символов русского языка это КОИ-8, КОИ-7 и др.

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

В настоящее время появился и находит все более широкое применение еще один международный стандарт кодировки -Unicode. Его особенность в том, что в нем использовано 16-битное кодирование, т.е. для представления каждого символа отводится 2 байта. Такая длина кода обеспечивает включения в первичный алфавит 65536 знаков. Это, в свою очередь, позволяет создать и использовать единую для всех распространенных алфавитов кодовую таблицу.

4.2.3. Алфавитное кодирование с неравной длительностью элементарных сигналов. Код Морзе.

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

Пусть  t- длительность импульса соответствует точке, тогда:

3t – соответствует тире

3t – пауза между буквами

t -  длительность паузы между точками, точкой и тире, между тире

6t – длительность пазы между словами и т.д.

Свой код Морзе разработал в 1838 г., т.е. задолго до исследований относительной частоты появления различных букв в текстах. При составлении кодов Морзе для букв русского алфавита учет относительной частоты букв не производился, что, естественно, повысило его избыточность.

4.2.4. Блочное двоичное кодирование

Наилучший результат (наименьшая избыточность) был получен при кодировании по методу Хаффмана для русского алфавита избыточность оказалась менее 1%. При этом указывалось, что код Хаффмана улучшить невозможно. На первый взгляд это противоречит первой теореме Шеннона, утверждающей, что всегда можно предложить способ кодирования, при котором избыточность будет сколь угодно малой величиной. На самом деле это противоречие возникло из-за того, что до сих пор мы ограничивали себя алфавитным кодированием.

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

Пусть имеется словарь некоторого языка, содержащий п =16000 слов (Это солидный словарный запас). Поставим в соответствие каждому слову равномерный двоичный код. Длину кода находится по формуле по ранее описанной формуле:

k ≥ Log21600 > 13,97 = 14.

Следовательно, каждое слово кодируется комбинацией из 14 нулей и единиц. В качестве примера закодируем несколько слов:

ИНФОРМАТИКА      10101011100110,

НАУКА                                   -00000000000001,

ИНТЕРЕСНАЯ                      00100000000010;

Тогда последовательность:

000000000000110101011100110000000000000001 будет означать «ИНФОРМАТИКА ИНТЕРЕСНАЯ НАУКА».

Установлено, что средней длине русского слова  равна 5,3 буквам, а с учетом пробела между словами, она станет равной  К=6,3 буквам

Средняя информация на знак первичного алфавита F=k/K=14/6,3 = 2,222 бит, что более чем в 2 раза меньше, чем 5 бит при равномерном алфавитном кодировании. Для английского языка такой метод кодирования дает 2,545 бит на знак. Таким образом, кодирование слов оказывается более выгодным, чем алфавитное.

Еще более эффективным окажется кодирование в том случае, если сначала установить относительную частоту появления различных слов в текстах и затем использовать код Хаффмана. Подобные исследования провел в свое время Шеннон: по относительным частотам 8727 наиболее употребительных в английском языке слов он установил, что средняя информация на знак первичного алфавита оказывается равной 2,15 бит.

Вместо слов можно кодировать сочетания букв блоки. В принципе блоки можно считать словами равной длины, не имеющими, однако, смыслового содержания. Блочное кодирование обеспечивает построение более оптимального кода, чем алфавитное. При использовании блоков большей длины (трехбуквенных и более) избыточность стремится к 0 в полном соответствии с первой теоремой Шеннона.

Алфавитное, т.е. побуквенное, кодирование можно задать таб­лицей кодов. Фактически кодом, кодирующей функцией, будет служить некоторая подстановка s:

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

Вторая строка – например,  кортежи из цифр 0 и 1 двоичное их представление.

Алфавитное ко­дирование можно использовать для любого множества сообщений, причем оно  является самым про­стым, и его всегда можно ввести на непустых алфавитах.

Обязательным  условием такого кодирования является установление взаимнооднозначного соответствия между наборами элементов первой и второй строки

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

5. Системы контроля кодирования

5.1. Система контроля.

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

Системой контроля   называется совокупность определенных методов и средств, обеспечиваю­щих необходимое качество работы как всей ЭВМ, так и отдель­ных ее элементов, а также автоматическое исправление возника­ющих ошибок называется

В задачи системы контроля надежности работы ЭВМ входят:

~    профилактический контроль, т.е. предупреждение появления возможных ошибок;

~    оперативный контроль  проверка качества выполнения ма­шинных операций.

Важно не только установить наличие ошибки, но и устранить ее с помощью ЭВМ. Поэтому разработа­ны различные методы кодирования, позволяющие решать постав­ленные задачи.

Несмотря на то, что надежность электронной аппаратуры по­стоянно возрастает, в работе ЭВМ неизбежны систематические и случайные ошибки. Искажение сигнала за счет помех канала связи может быть вызвано повреждением поверхности магнитного но­сителя и потерей контакта.

Будем рассматривать канал связи с помехами как модель раз­личных ошибок. Пусть заданы алфавиты А = В= {0, 1}и  Λ  пустое слово, а кодирование выполняется без дополнительных помех. Возможны три типа ошибок:

~                          0 ® 1, 1 ® 0  ошибки замещения разряда;

~                          0 ® Λ, 1 ® Λ  ошибки выпадения разряда (длина слова уменьшается на 1);

~                          Λ ® 1, Λ ®0  ошибки вставки разряда (длина слова увели­чивается на 1).

Общая характеристика ошибок канала, т. е. их количество и тип, обозначается Q. Так, канал с характеристикой Q = (1, 1,0) озна­чает, что в канале возможны по одной ошибке замещения и вы­падения разряда при передаче сообщения.

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

Ключ - информация, необходимая для беспрепятственного шифрования и дешифрования текстов.

К основным видам криптосистем относят симметричные и си­стемы с открытым ключом. Симметричные криптосистемы исполь­зуют единый ключ для шифрования и дешифрования информации. На рисунке показана схема процесса дешифрования

Системы с открытым ключом подразумевают также и наличие закрытого ключа, доступного лишь получателю сообщения.

Криптостойкость ключа означает его способность противо­стоять крипто анализу.

На современные криптографические систе­мы защиты информации накладываются общепринятые требова­ния, среди которых важнейшими являются следующие:

~                          зашифрованное сообщение поддается прочтению только с помощью ключа;

~                         любые изменения ключа влекут за собой значительные изме­нения зашифрованного сообщения;

~                          структура алгоритма, информация  постоянны;

~                         длина зашифрованного текста равна длине исходного текста;

~                         алгоритм должен допускать различные виды реализации (про­граммный и (или) аппаратный).

Задачей теории кодирования является проблема наилучшего согласования источника информации и канала связи. Симметрич­ные криптосистемы включают в себя в числе других подстановки, перестановки и блочные шифры. При подстановке происходит за­мена символов исходного текста буквами того же алфавита. При этом шифруется каждый символ исходного текста.

Самый древний из известных видов шифрования подстановки Цезаря (I в. до н.э.). Этот код назван в честь знаменитого римского императора Гая Юлия Цезаря, поручившего Цицерону составить по­слания с использованием пятибуквенного алфавита. Подстановка Це­заря заключалась в замене символов (букв) исходного текста алфави­том, смещенным на три буквы вправо. Очевидно, сопоставление алфа­витов делает код Цезаря легко поддающимся вскрытию.

5.2. Эффективное кодирование.

Закодируем сообщение, записан­ное с помощью алфавита, содержащего п символов, например с помощью русского алфавита, содержащего 33 буквы и знаки пре­пинания. Чтобы закодировать это сообщение, необходимо указать правило, которое устанавливает взаимнооднозначное соответствие между самим сообщением и теми кортежами из т символов, ко­торыми оно записано в этом алфавите.

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

Как известно, возможность эффективного использования лишь двух символов 0 и 1 для кодирования указал Фрэнсис Бэкон. Он первым применил в XVI в. принцип двоичного кодирования для маскировки тайнописи. Так, Бэкон, передавая сообщения с помощью букв А и В, зако­дировал пятерками, состоящими из этих букв, весь латинский алфавит. Как известно, Лейбниц использовал принцип двоичного кодирования не только в своей двоичной арифметике, но также и в так называемой двухзначной логике.

Кодирование информации преследует разные цели и поэтому использует различные методы. В качестве целей могут служить:

~    экономичность, т.е. уменьшение избыточности сообщений;

~     обеспечение максимальной пропускной способности канала связи;

~    надежность, т.е. защита сообщений от случайных искажений, помехоустойчивое кодирование;

~    сохранность, т.е. защита информации от постороннего досту­па к ней;

~     повышение скорости передачи информации;

~    удобство физической реализации через соответствующие сред­ства связи;

~     удобство восприятия сообщений.

Иногда эти цели вступают в противоречие друг с другом. Так, надежность кода требует избыточности информации, а это неэко­номично. Такую избыточную информацию содержат, например, многие финансовые документы, где денежную сумму записывают и числом, и прописью.

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

5.3.Методы эффективного кодирования информации.

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

Один из самых эффективных путей кодирования основан на применении основной теоремы Шенно­на для каналов без шума. Согласно этой теореме сообщение, со­ставленное из букв некоторого алфавита, можно закодировать так, что среднее число двоичных символов на букву будет сколь угодно близко к энтропии источника этих сообщений, но не меньше этой величины. Это означает, что при выборе каждого символа кодо­вой комбинации необходимо добиваться, чтобы знак нес макси­мальную информацию, т.е. принятие каждым символом значений 0 и 1 должно быть равновероятным, и этот выбор не должен зави­сеть от предыдущих значений символов. По имени авторов первых эффективных методов кодирования этот код получил название метода Шеннона -  Фано.

Кодирование само по себе не гарантирует 100 %- ной защиты при передаче информации. Иска­жение информации может происходить по различным причинам от помех или шумов, которые могут быть вызваны различными обстоятельствами, такими, как неисправность ЭВМ, отклонение от стандартов напряжения сети или влажности помещения, вне­шние помехи и др.

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

1. Погрешности в данных,

2. Методические погрешности

3. Неисправности в работе ЭВМ.

Ошиб­ки первого и второго вида система контроля не сможет исправить самостоятельно, их надо учесть заранее.

Помехами в канале связи называется потеря информации меж­ду входом и выходом, связанная с самим каналом.

В задачи помехоустойчивого кодирования входит обнаружение и исправление ошибок третьего вида. Эта цель достигается введе­нием избыточной информации. Избыточность информации можно получить аппаратными (схемными), логическими и информаци­онными средствами.

Конечно, для обнаружения ошибки можно перепроверить ре­зультат другим способом, например, применив другой математи­ческий метод. Но эта перепроверка сможет только установить на­личие ошибки.

Другой способ обнаружения ошибки заключается в удвоении каждого символа. Например, слово март можно закодировать в слово ммаарртт. Тогда, в случае искажения одного из символов, ошибку можно обнаружить по второму, неискаженному символу. Так, получив искаженное слово ммаарртс, мы должны прове­рить оба варианта гипотез: марс и март.

При кодировании неизбежно возникает избыточная информа­ция (шум), поэтому ставится задача сведения этой избыточности к минимуму.

Существует несколько десятков разнообраз­ных методов распознавания и коррекции ошибок кодирования, предназначенных для каналов связи с различными характеристи­ками помех.

Выдающимся достижением в теории кодирования являются теоремы, сформулированные и доказанные Клодом Шенноном, о том, что при любых помехах и шумах возможна передача ин­формации с минимумом потерь. Оговоримся, что здесь мы дадим популярную интерпретацию теорем Шеннона, так как их факти­ческая формулировка оперирует с такими понятиями теории ве­роятностей, как условная вероятность, условное распределе­ние, и выходит далеко за рамки вузовской программы. Строгое доказательство теорем основано на неравенстве Фано.

Согласно первой теореме Шеннона, если канал передачи не содержит собственных помех, то, возможно, так закодировать со­общение, чтобы среднее число элементов кода (двоичных симво­лов), приходящихся на один элемент кодируемого алфавита, было минимальным. Это так называемое эффективное статистическое кодирование.

Первая теорема Шеннона утверждает, что вероятность ошибок при передаче информации сколь угодно мала, если энтропия S множества передаваемых сообщений меньше пропускной способ­ности канала связи С, определяемой как наибольшее число бит, которые возможно передавать по этому каналу связи за единицу времени.

Для каналов связи с помехами справедлива вторая теорема Шеннона (прямая теорема кодирования. Согласно которой всегда существует способ кодирования, такой, что информация, может быть передана с какой угодно высокой достоверностью при боль­шой длине передаваемых слов, если скорость передачи не выше пропускной способности канала связи.

Вторая теорема Шеннона доказывает принци­пиальную возможность помехоустойчивого кодирования.

Сформулируем три глобальные проблемы кодирования:

1.  Создание шифра кодирования;

2.  Создание специальных корректирующих кодов для поиска и исправления ошибок, возникающих в результате передачи и хра­нения информации;

3.  Минимизация избыточной информации для успешной кор­рекции и сокращения потерь в скорости передачи сообщения.

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

Необходимо максимально снизить уровень помех и максималь­но повысить уровень полезного сигнала, т. е. увеличить отношение сигнал/шум. Увеличение отношения сигнал/шум может достигаться за счет представления информации в виде импульсов, четко вы­деляемых на фоне помех.

В целях борьбы с помехами используется фильтрация инфор­мации, принимаемой на выходе канала связи.

Борьба с помехами уменьшает, но не исключает вероятность появления ошибок. Что бы их учесть или ликвидировать вводятся различные способы кодирования, которые учитывают вероятность ошибок и при их обнаружении, либо их устраняют, либо выдают соответствующее сообщение. К таковым кодам относятся корректирующие коды, систематические коды и контроль по четности. Учитывая достаточно высокую их абстрактность и сложность, ограничимся лишь некоторыми общими положения о них

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

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

Систематические коды. Такие коды  состоят из двух частей:

Первая часть содержит  k – контролирующих разрядов.

Вторая часть содержит m – информационных разрядов.

Причем m+k=n – число разрядов в информационном слове.

Корректирующая способность такого кода численно равна  вероятности обнаружения  и исправления ошибки.

При передаче двоичных сообщений ошибка может заключаться только в замене 0 на 1 или 1 на 0. Складывая (по модулю 2) соответствующие разряды оригинала и полученного сообщения поразрядно, можно установить ошибки. Если получили 0, то ошибок нет, если получили 1, то ошибка есть. Причем видно, что те разряды, которые  в сумме дают 1, то ошибка именно в этом разряде. Передав повторно полученное ошибочное сообщение, согласно двойной инверсии получим верное сообщение.

Остается установить, каким образом перееденное сообщение сравнивается с оригиналом, который остался  в первоначальном месте. На этот счет есть  первая часть сообщения, которая имеет информации о передуваемом слове, например, наличие в нем единиц – вес сообщения. Если вес сообщения не совпадает с весом полученного слова, то произошла ошибка.

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

Для уменьшения вероятности ошибки в двоичных кодах ис­пользуют код Грея, в котором каждые две позиции отличаются только одним разрядом, т.е. на 1 бит. Поэтому выходной сигнал может быть представлен лишь одним из двух состояний  истин­ным или ложным.

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

Замечание. Рассмотренные коды дают информации об одной ошибке. Но ошибок может быть несколько. Причем исправление одной из них, может привести к появлению дополнительных ошибок.

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

6. Кодирование и обработка чисел компьютером

Для представления чисел в компьютере и выполнения над ними арифметических действий числа кодируются с помощью нулей и единиц.  Способы кодирования чисел и допустимые над ними действия зависят от принадлежности таковых чисел  к следующим числовым множествам:

  1. Целые положительные числа (целые числа без знака);
  2. Целые числа со знаком;
  3. Вещественные нормализованные числа.

Кодирование в компьютере целых положительных чисел

Для записи числа в устройствах компьютера выделяется фиксированное количество двоичных разрядов. Память компьютера имеет байтовую структуру, однако, размер одной адресуемой ячейки обычно составляет несколько байт. В компьютерах IBM ячейка памяти объединяет 2 байта (16 двоичных разрядов), что называется машинным словом

Машинное слово  комбинация связанных соседних ячеек, обрабатываемая совместно

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

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

Пусть количество разрядов k=16. При двоичном кодировании число символов p=2, это 0 и 1. Максимальное число, закодированное  ими равно:

Хmax= 1111111111111112 1

Для определения самого числа воспользуемся формулой

Хmax=pk- 1, для k=16 и  p=2, получим  Хma = 216- 1 = 65536- 1=65535

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

Минимальным целым числом является число

Хmin = 0000000000000002 = 010.

В языках программирования (PASCAL)  для записи целых чисел без знака, отводится 2 байта, и они определены как тип Word. Тип устанавливает способ кодирования числа, количество отводимых для записи ячеек памяти (т.е. разрядность числа), а также перечень допустимых операций при обработке.

Выход за границу числа 65535 возможен только путем увеличения количества разрядов для записи числа, но это порождает новый тип  кодирования чисел. Если машинное слово занимает 4 бита, что максимальное число, которое будет закодировано,  можно вычислить по той же самой формуле,  и оно будет равно: Хmax =  2147483647.

Кодирование в компьютере целых отрицательных чисел

В вычислительной технике при использовании двоичной системы счисления крайний левый разряд в машинном слове служит для записи знака числа. При  этом условились кодировать:

- знак  плюс или положительное число  нулем,

- знак минус или отрицательное число  единицей.

Такое представление чисел называется прямым кодом.

Под запись самого числа остается 16- 1=15 двоичных разрядов, что обеспечивает наибольшее значение числа Zmax= 215-  1 = 3276710.

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

Альтернативным вариантом является представление чисел со знаком в дополнительном коде. Идея построения дополнительного кода достаточно проста: на оси целых положительных чисел, помещающихся в машинное слово на промежутке (0; 65535), сместим положение нуля на середину интервала.

Числа, попадающие в первую половину (0; 32767) считаются  положительными, а числа из второй половины (32768; 65535)  отрицательными.

В этом случае судить о знаке числа можно будет по его величине и в явном виде выделение знака не потребуется.

Например, число 1000000000000012 = 3276910 -  отрицательное числа,

число 0000000000000012 = 110 положительное  число.

Принадлежность к интервалу кодов положительных или отрицательных чисел видна по состоянию старшего бита  у кодов положительных чисел его значение 0 отрицательных – 1. Это напоминает представление со знаком, но не является таковым, поскольку используется другой принцип кодирования. Его применение позволяет заменить вычитание чисел их суммированием в дополнительном коде.

Кодирование вещественных нормализованных чисел.

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

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

Число Х10 называется нормализованным, если оно представлено в виде

Х10=±М10 ·10± k,  где 0,1 < М10 < 1, k  целое положительное  число.

М10   мантисса нормализованного числа, k  порядок нормализованного числа. Очевидно, что первая значащая цифра мантиссы всегда ненулевая

Задание 8- 62. Представить в нормализованном виде числа: 1234, 0,03456

Решение и ответ: 1234 = 0,1234·10; 0,03456 = 0,3456·102.

Понятие нормализованного числа следует отличать от понятия числа в нормальной форме; часто используется при записи чисел в математике, физике, технических дисциплинах и отличается от нормализованного представления тем, что мантисса лежит в интервале 1 < М10 < 10, например Х =1,38- 1023.

При нормализации происходит установление его составляющих элементов:

Определение знака числа,

2. Выделение мантиссы,

3. Установление знака порядка

4. Вычисление числового значения порядка

Аналогично нормализации десятичного числа можно в нормализованной форме представить и число в произвольной системе счисленияq:

Хq = ±Мq ·10± k или Хq = ±(М ·10± k)q,  где мантиссы лежат в интервале (q- 1;1) (т.е. первая значащая цифра мантиссы всегда ненулевая), а показатель степени k – коэффициент  представляется в заданной системе q.

Задание 8- 63. Записать числа в нормализованной форме:  101,012

Ответ с комментариями: q = 2: Х2 = - 101,012 = 0,101012 ·211

Другая форма записи: Х2= - 101,012 = (0,10101 ·211)2

Запятая перенесена влево на 3=112 знака, т.е. k=112. Мантисса располагается в промежутке (0,12; 12), что соответствует десятичному интервалу (0,5;1)

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

Задание 8- 65. Выполнить перевод числа из десятичной системы счисления в нормализованную двоичную систему счисления.

Х10=16,5 перевести в Х2 – нормализованную форму.

Решение. 1610=100002,  0,510=0,12.  16,5 =10000,12=(0,100001·2101)2

Ответ: (0,100001·2101)2

Задание 8- 66. Выполнить перевод числа из нормализованной двоичной системы счисления в  десятичную систему счисления.

Х2=(0,11·2110)2 перевести в десятичную систему счисления.

Решение.

1 способ  0,112 =2- 1+2- 2= 0,5+0,25=0,75;    2110=26=6410,  0,75·64=48

2 способ. k=1102 = 610 , Перенеся  в числе 0,112 знак на 6 разрядов вправо, получим число 1100002= 25+24=32+16=48.

Ответ. 48.

Выполнение арифметических действий проводится согласно правилам двоичной арифметики. Рассмотрим некоторые из них.

Сложение.

Сложение двух чисел проводится согласно таблице сложения, способ составления токовых таблиц был рассмотрен ранее

Таблица

сложения q=2

0 1
0 0 1
1 1 10

Из этой таблицы сложения следует, что:

0+0= 0   0+1=1 1+0= 1            1+1 =10

В последнем случае в том разряде, где находились слагаемые, оказывается 0, а 1 переносится в старший разряд. В связи с этим вводится дополнительное  понятие -  единицы переноса или биты переноса.  Они появляются в результате переполнения  того или некоторого разряда. Если это происходит, то над такими разрядами ставится  метка, показывающая такое переполнение. С появлением единиц переноса возникает необходимость составления таблицы для трех слагаемых

Разрядные единицы Сумма Разрядные  единицы Сумма
0 0 0 0 1 1 0 10
1 0 0 1 1 0 1 10
0 1 0 1 0 1 1 10
0 0 1 1 1 1 1 11

Алгоритм сложения аналогичен сложению чисел в десятичной арифметике.

Задание 8-67. Выполнить сложение чисел 341+115 в двоичной системе счисления, фиксируя единицы переноса.

Решение 341 = 1010101012, 115=1100112

S= 1010101012 + 11100112

1 1 1   1  1 1                          единицы переноса

1 0 1 0 1 0 1 0  1                        первое слагаемое

+ 1 1 1 0 0 1 1   второе слагаемое

1 1 1  0 0 1 0 0 0                       полученная сумма

Сложение начинается с единиц младшего разряда – правый крайний.

1+1=10, 0 пишем под чертой, 1 –  над единицами следующего разряда, она переносится в следующий разряд.

Аналогично выполняется сложения последующих разрядных единиц

Ответ: 341+115 =1010101012 + 11100112=1110010002=456

Сложение чисел в восьмеричной и шестнадцатеричной  системе выполняется аналогично двоичной арифметике.

Задание 8- 68. Выполнить сложение чисел 34478+70458

Решение

11                                единицы переноса

3447                  первое слагаемое

+ 7045   первое слагаемое

12514                   полученная сумма

Ответ: 34478+70458=125148

Вычитание

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

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

Задание 8- 69. Выполнить вычитание, заменив его сложением

а). 85- 37 = 85 + (100- 37)= 85+63=148, отнимается единица из старшего  разряда, 148 100 = 48. Ответ 85- 37=48

б). 567 – 156= 567+(1000- 156)=567+844=1411, 1411- 1000=411. Ответ: 411.

В вычислительной технике при замене вычитания сложением вводится дополнительный код. При этом саму операцию вычитания можно представить как алгебраическую операцию сложении, вычитание заменяется прибавлением противоположного числа: a – b = a + (- b)

Рассмотрим составление дополнительного кода к прямому коду отрицательного числа, а именно, когда целое число кодируется 0 или 1 в старшем разряде (последнем слева)  на примере вычитания чисел:

101102- 11012=101102- 011012

  1. Уменьшаемое 101102 представляется в прямом коде как положительное число, дл этого добавляется цифра 0 впереди старшего разряда, обозначим ее другим шрифтом 0 101102.
  2. Вычитаемое 011012 представляется в прямом коде как отрицательное число, дл этого добавляется цифра  1 впереди старшего разряда, обозначим ее другим шрифтом 1 011012.
  3. Определяется дополнительный код вычитаемого, для этого:

а).      Инвертируется вычитаемое, а именно во всех разрядах вычитаемого, кроме знакового разряда, нули заменяются единицами и единицы – нулями. Получили число 1 100102.

б).      Прибавляется единица к младшему разряду  1 100102+1= 1 10011

3. Выполняется сложение чисел, полученных в пункта 1 и 3б:

0 101102  первое слагаемое, бывшее уменьшаемое (прямой код)

+ 1 100112  второе слагаемое, бывшее вычитаемое (дополнительный код)

10 01001    отбрасывая левую крайнюю единицу знаковых разрядов, получим  результат вычисления:  0 010012    в прямом коде, кстати, оно, согласно разряду кодов  положительное число.

Правильность вычислений можно проверить в прямом коде, сложив числа:

011012+010012=101102

Умножение

Умножение производится согласно таблице умножения

Таблица

умножения q=2

0 1
0 0 0
1 0 1

Из таблицы умножения  следует, что:

0·0=0     0·1=0    1·0=0       1·1 =1

Выполним умножение 10102·1012

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

Деление.

Деление сводится к операции вычитания, которая выполняется несколько раз со сдвигом. Эта операция очень трудоемкая и рассматриваться в двоичной арифметике в данном курсе не будет. Покажем выполнения  деление на основе вычитания и сдвига в десятичной арифметике:

132: 11.

132- 110=22 –первое вычитание. 22< 110 выполняется первый сдвиг

22- 11=1       первое вычитание после первого сдвига

11- 11=0       второе вычитание после первого сдвига

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

Вычислительные машины выполняют арифметические действия в значительно более трудных условиях,  чем те которые были рассмотрены. ЭВМ работает с любыми числами и практически с любым количеством цифр в нем Дл этого разработаны очень сложные методы и приемы вычислений с достаточно высокой точностью получаемого результата.

В знаковых разрядах, например,  может быть две цифры, причем 00 соответствует  положительному числу, 11 – отрицательному числа, 01 или 10 говорит о том, что произошло переполнения разрядной сетки.

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

Ситуация меняется при представлении и обработке вещественных чисел. На числовой оси вещественные числа образуют непрерывное множество (континуум), т.е. два числа могут находиться сколь угодно близко друг к другу, и на любом отрезке содержится бесконечно много значений чисел. В машинном представлении количество возможных значений чисел конечно; для двоичной системы счисления оно определяется как 2k, где k - количество двоичных разрядов в представлении мантиссы. Т.е. вещественные числа в компьютере заменяются их кодами, которые образуют конечное дискретное множество, каждый код оказывается представителем целого интервала значений континуума.

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

Основной формой представления кодов вещественных чисел в компьютере является двоичная нормализованная форма. Записываться и храниться в памяти компьютера должны все составляющие нормализованной формы (знак числа, мантисса, знак порядка и порядок), что требует несколь­ких ячеек памяти.

Непосредственное распределение компонентов нормали­зованного числа по разрядам определяется конструктивными особенностями компьютера и программным обеспечением.

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

В процессе выполнения арифметических действий с нормализованными числами отдельно обрабатываются мантиссы и порядки.

Контрольные вопросы

1. Привести исторические сведения о кодировании.

2. Определение системы счисления.

3. Общая формула записи числа

4. Алгоритмы перевода числа из системы счисления q=10 в иную систему и наоборот.

5. Перевод дробей в различные системы счисления.

6. Правила выполнения арифметических действий в различных системах счисления.

7. Понятие смешанных систем счисления  практическое их применения.

8. Связь между системами счисления с основаниями q=2n

9. Понятие об измерении информации.

10.Перечислить основные понятия, связанные с кодированием.

11.Сформулировать  теоремы Шеннона.

12.Алфавитное кодирование

13.Особенности алфавитного неравномерного двоичного кодирования сигналами равной длительности.

14.Придумать неравномерные коды первых 10 букв русского алфавита.

15.Дать общую характеристику кодирования по методу Хаффмана.

16.Система контроля кодирования

17.Кодирование в компьютере целых положительных и отрицательных чисел

Требования к знаниям умениям и навыкам.

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


[1] Англ, binary digit -  двоичное число.

[2] Египетская легенда. Бар- Кохба (сын звезды) -  предводитель восста­ния против римлян имевший немого разведчика, который по разведки отвечал на односложные вопросы кивком головы