Теория информации и кодирования: логические основы ЭВМ

Следующим существенным прорывом вперёд в технологии телеграфа был примитивный печатающий телеграфный аппарат, или "телетайп"; его запатентовал во Франции в 1874-м году Жан Морис Эмиль Бодо (1845-1903). Как и телеграф Морзе, это изобретение привело к созданию новой системы кодирования символов - 5-битного метода кодирования Бодо. Метод кодирования Бодо стал первым в мире методом кодирования текстовых данных с помощью двоичных последовательностей. Сообщения, для передачи которых использовалась система кодирования Бодо, распечатывались операторами на узкие ленты для двухканальной связи с помощью специальных 5-клавишных клавиатур. В более поздних версиях устройства использовались клавиатуры с буквами, которые уже автоматически генерировали соответствующую той или иной букве 5-битную последовательность. Другой особенностью телетайпа Бодо было мультиплексирование, обеспечивающее возможность одновременной работы до 6-ти операторов благодаря применению системы временного распределения. Это позволило значительно увеличить пропускную способность телеграфной линии. Предложенная Бодо аппаратура зарекомендовала себя весьма положительно и оставалась в широком применении в XX-м веке, пока её не вытеснили телефоны и персональные компьютеры. 1890-й год: американское Бюро статистики и появление в нём новой системы для кодирования символов.

Конец XIX-го века ознаменовался изобретением ещё одной системы для кодирования символов естественных языков. Он была создана в США для обработки данных, собираемых во время переписей населения, молодым американским* изобретателем, которого звали Герман Холлерит (1860-1929). После окончания Нью-Йоркской Колумбийской школы горного дела в 1879-м году, в 1880-м Холлерит устроился на работу в Бюро статистики при Министерстве внутренних дел США. Последствия этого, казалось бы, незначительного события сказывались впоследствии вплоть до 1970-х годов, "золотой эры" больших вычислительных машин. Герман Холлерит был ни кем иным, как изобретателем кода Холлерита, использовавшегося для записи алфавитно-цифровой информации на бумажных перфорированных картах. С появлением перфокарт в американских массах возникло шуточное выражение 'do not fold, spindle, or mutilate' ("не гнуть, не тянуть, не мять"), которое оставляло у многих американцев впечатление, что компьютеры скоро будут полностью контролировать их общество.

В системе кодирования Холлерита, на первый взгляд, двоичная последовательность, соответствующая одному алфавитно-цифровому символу, регистрировалась в 12-ти горизонтальных рядах перфокарты, и поскольку каждый из рядов мог быть перфорирован или не перфорирован (содержать 1 или 0), это давало бы 12-битный метод кодирования. Максимально возможное количество элементов, которое могло бы быть представлено с помощью такого метода кодирования - 212, то есть 4096. На самом же деле таблица символов, используемая в системе Холлерита, содержала только 69 символов - это были заглавные латинские буквы, арабские цифры, знаки препинания и некоторые другие символы. Таким образом, реальные возможности системы кодирования Холлерита по представлению текстовых данных были сравнимы даже с таковыми возможностями системы кодирования Бодо. Зачем же тогда, спросит читатель, на перфокарте было предусмотрено так много горизонтальных рядов? Одной из причин этому является тот факт, что большее количество рядов позволяет кодировать данные, производя меньшее количество перфораций, а это было критично, так как работа с перфораторами карт в течение многих лет производилась вручную. Поскольку рядов было много, для кодирования каждой из 10 арабских цифр (а также 2-х букв латинского алфавита) было достаточно сделать всего одну перфорацию на один вертикальный ряд. Оставшиеся 24 буквы латинского алфавита кодировались с помощью двух перфораций. Для кодирования знаков препинания и прочих символов требовалось сделать 2 или больше перфораций, поэтому нередко они  вообще не использовались.

 

 

 

 

 

Таблица 1

Система основных понятий

Представления информации
Языки представления информации
Естественные: русский, китайский, английский и др.			Формальные: язык математики, нотная грамота, языки программирования и др.
Кодирование
Цели кодирования
Засекречивание информации	Быстрый способ записи	Передача по техн. каналам связи		Выполнение математических вычислений
Шифрование	Стенография	Телеграфный код		Система счисления
Алгоритмы криптографий	Один знак – слово или сочетания букв	Код Морзе: неравномерный, троичный код	Код Бодо: равномерный, двоичный код	Для человека: десятичная с. с.	Для компьютера двоичная: с. с.

 

 

3. Логические основы ЭВМ

 

Умение правильно рассуждать необходимо в любой области человеческой деятельности: науке и технике, управлении, планировании, юстиции и дипломатии, военном деле и т.д. Это умение восходит к древним временам. Ответ на вопрос, какие формы рассуждений являются правильными, а какие неправильными, был дан в логике. Логика - это науке о формах и закона мышления, возникла в IV веке до нашей эры в работах великого греческого философа Аристотеля, который по праву считается основателем логики. Аристотель исследовал различные формы человеческого мышления, ввел в рассмотрение логики такие формы мысли как “понятие”, “суждение” и “умозаключение”, разработал теорию умозаключений и доказательств, введя понятие силлогизма, то есть такого рассуждения, в котором из заданных двух суждений выводится третье суждение. Примером силлогизма может быть такое рассуждение: “Все млекопитающие имеют скелет. Все киты - млекопитающие. Следовательно,  все киты имеют скелет”. В общем виде, силлогизмы имеют форму: “Все A суть B; все B суть C. Следовательно, все A суть C”. Некоторые силлогизмы являются правильными, некоторые силлогизмы могут быть неправильными. Так, например, силлогизм: “Юрий мой друг. Все мои друзья пошли в театр. Юрий смотрит спектакль” является верным, а силлогизм: “Все мои друзья пошли в театр. Юрий смотрит спектакль. Юрий мой друг” является неверным. С помощью комбинаторики доказано, что общее число силлогизмов, которые можно составить из суждений указанного выше вида, равно 256. Из них правильными являются лишь только 24.

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

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

2. Закон не противоречия (противоречия) - одно и тоже нельзя одновременно утверждать и отрицать.

3. Закон исключенного  третьего (tertium nondatur) - каждое высказывание непременно должно быть либо истинным, либо ложным.

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

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

 4. Закон двойного отрицания - если отрицание утверждения ложно, то исходное утверждение истинно.

5. Закон достаточных  оснований (Г. Лейбниц) - любое утверждение должно предполагать наличие аргументов и фактов, достаточных для его обоснования. Иными словами, что каждая истина должна быть обоснованной.

6. Принцип выбора - если всегда истинно одно  из утверждений А либо В (то есть одновременно они не могут быть истинны), но истинность В не выполняется, то должна выполняться истинность утверждения А.

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

Элементы теории силлогизмов. Теория силлогизмов до середины XX века входила составной частью во многие учебные программы образовательных заведений как гуманитарного, так и естественнонаучного направления. Рассмотрим кратко некоторые элементы теории силлогизмов. Само название этого раздела классической логики произошло от слова силлогизм (от греческого - sillogismos - категорический), такого дедуктивного умозаключения, в котором из двух суждений, имеющих, так называемую, субъективно-предикатную форму следует новое суждение, имеющее также субъективно-предикатную форму (“Все S суть P”; “Ни одно S не есть P”; “Некоторые S суть P”; “Некоторые S не есть P”).

Под субъективно-предикатной формой (от лат. Proedicatum - сказанное) понимается языковое выражение, обозначающее некоторое свойство рассматриваемого предмета (субъекта) или отношения, которым он подчиняется. Такое обозначение указанных суждений вытекает также из грамматического построения суждений и утверждений: там есть подлежащее (англ. - subject) и сказуемое (англ. - predicate). Только в логике понятия субъекта и предиката понимается в более широком смысле, чем в грамматике. “Субъектами” могут быть дополнения, местоимения и существительные, о которых что-то говорится, а “предикатами” могут быть обстоятельства и наречия.

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

Проанализировали историю возникновения: информации, кодирования, логических основ кодирования.  Изучили понятия, суть, применения.

РАЗДЕЛ 2.  ПРАКТИЧЕСКИЕ АСПЕКТЫ АЛГОРИТМЫ КОДИРОВАНИЯ ИНФОРМАЦИИ

 

Для любой ЭВМ ввод информации и программ должен записываться на

«языке» понятном ЭВМ. Таким понятным «языком» является двоичная система, представляемая единичками и нулями в соответствующих ячейках памяти ЭВМ. То есть все операнды и команды запоминаются в виде нулей и единиц в определенной последовательности. Если использовать 8 двоичных разрядов (байт), то легко подсчитать, что число возможных комбинаций допустимых значений “0 ” или “1” в одном байте равно 28 = 256 (0 до 255). Действительно, максимально возможное двоичное число равно 1111 11112 . Для представления его в десятичном виде получим 1111 11112=(1111 11112+1)-1=1000000-1=2^8-1=255. Поэтому каждый символ-буква какого-либо алфавита, цифра, знак пунктуации или арифметического действия кодируется определенной последовательностью двоичных цифр в соответствии с принятой таблицей кодирования. Наиболее распространенными таблицами кодирования информации являются таблицы: ДКОИ, КОИ-8, ASCII. Отличия их состоит в том, что в них для представления символов используется различное количество разрядов. В последнее время для кодирования информации все чаще используется таблица UNICODE, использующая для кодировки 2 байта. То есть в кодировке UNICODE можно закодировать 65536 различных символов. Как видно, в одном байте можно хранить одно из 256 целых чисел от 0 до 255 . Этого вполне достаточно для того, чтобы дать уникальное 8-битовое обозначение каждому символу, применяемому в языке программирования. Для представления чисел в памяти ЭВМ выделяется определенное количество битов, независимо от конкретных значений чисел. Такое представление называют кодом числа. Код числа, в зависимости от выбранной формы, всегда имеет фиксированное количество двоичных цифр. В отличие от нумерации разрядов числа, биты в байте нумеруются слева направо от 0 до 7 . Каждый байт в памяти ЭВМ имеет свой порядковый номер, который называется абсолютным адресом байта. Байт является основной единицей хранения данных и наименьшей адресуемой единицей обмена информации в оперативной памяти ЭВМ, то есть минимальной единицей обмена информации, имеющей адрес в памяти ЭВМ.

Последовательность нескольких смежных байтов образует поле данных. Количество байтов поля называется длиной поля, а адрес самого левого байта поля - адресом поля. Байты нумеруются слева направо, начиная с 0 . Обработка информации может вестись либо побайтно, либо полями данных (или форматом данных). Форматы данных показывают, как информация размещается в оперативной памяти и регистрах ЭВМ. Форматы данных различают по - длине, типу данных и структуре. Различают поля фиксированной и переменной длины. Длину формата данных измеряют в машинных словах или целым количестве битов. Минимальным полем фиксированной длины является полуслово. Полуслово состоит из двух последовательных байтов (16 бит, пронумерованных слева направо от 0 до 15). Два полуслова образуют слово. Слово состоит из четырех последовательных байтов (32 бита, пронумерованных слева направо от 0 до 31). Два слова образуют двойное слово (64 бита, пронумерованных слева направо от 0 до 63). В ПЭВМ слово, это, как правило, 2 байта, а двойное слово - 4 байта. Поле переменной длины может быть любой длины в пределах от одного до 256 байтов (нумерация от 0 до 255 ). Форматы полей данных, используемых в ЭВМ, представлены в таблицах 2.1, 2.2. Если в указанных форматах размещаются числа, то веса их разрядов возрастают справа налево.

Таблица 2

Формат данных фиксированной длины.

0	7	8	15	16	23	24	31	32	39	40	47	48	55	56	63
Байт		Байт		Байт		Байт		Байт		Байт		Байт		Байт
Полуслово				Полуслово				Полуслово				Полуслово
Слово								Слово
Двойное слово

 

 

 

 

 

Таблица 3

Формат данных переменной длины.

Байт	Байт	Байт	Байт	Байт	….	Байт
0	1	2	3	4	….	255