Основные понятия и методы теории информации и кодирования

1.

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО
ОБРАЗОВАНИЯ
«СИБИРСКИЙ ГОСУДАРСТВЕННЫЙ АВТОМОБИЛЬНО-ДОРОЖНЫЙ УНИВЕРСИТЕТ (СИБАДИ)»
КАФЕДРА «ЦИФРОВЫЕ ТЕХНОЛОГИИ»
ЛЕКЦИЯ 1: ОСНОВНЫЕ ПОНЯТИЯ И
МЕТОДЫ ТЕОРИИ ИНФОРМАЦИИ И
КОДИРОВАНИЯ
СТАРШИЙ ПРЕПОДАВАТЕЛЬ:
ОТС ДАРЬЯ АНАТОЛЬЕВНА
ОМСК-2023

2.

СТРУКТУРА ЛЕКЦИИ
1. Информация. Информационные процессы: Понятие
информации. Виды информации. Свойства информации. Единицы
измерения информации. Процессы хранения, обработки и передачи
информации.
2. Кодирование информации: Кодирование текстовой,
графической, звуковой, видеоинформации. Системы счисления (СС)
для числовой информации. Алгоритмы перевода между СС.
Арифметические операции над числами в различных СС.
3. Информационно-логические основы ЭВМ: Представление
информации в памяти ЭВМ. Основные понятия формальной логики.
Логические операции: конъюнкция, дизъюнкция, инверсия,
импликация, эквиваленция. Выполнение логических операций.
Таблицы истинности. Законы алгебры логики.
2

3.

ПОНЯТИЕ ИНФОРМАЦИИ
Информация – все сведения, являющиеся объектом хранения,
передачи и преобразования. Это сведения, передаваемые одними
людьми другим людям устным, письменным или каким-нибудь
другим способом;
Носитель информации – материальная среда для записи,
хранения и передачи информации;
Сигнал – изменяющийся во времени физический процесс;
Параметр сигнала - характеристика, которая используется для
представления данных. Если параметр сигнала принимает ряд
последовательных значений и их конечное число, то сигнал
называется дискретным. Если параметр сигнала – непрерывная во
времени функция, то сигнал называется непрерывным.
3

4.

СВОЙСТВА ИНФОРМАЦИИ
Качество информации является
параметров для потребителя информации.
одним
из
важнейших
Оно определяется следующими свойствами:
Репрезентативность;
Достаточность;
Доступность;
Актуальность;
Своевременность;
Точность;
Адекватность;
Устойчивость.
ЗАДАНИЕ 1
Записать в конспект свойства
информации и найти пояснения
к каждому определению!
4

5.

КЛАССИФИКАЦИЯ ИНФОРМАЦИИ
по способам восприятия: визуальная (при помощи органов
зрения), аудиальная (при помощи органов слуха), тактильная
(осязание), обонятельная, вкусовая;
по форме представления: текстовая, числовая, графическая,
звуковая, комбинированная (мультимедийная);
по общественному значению: общественная (обыденная,
общественно-политическая, эстетическая), специальная (научная,
производственная, техническая, управленческая), личная (знания,
умения, интуиция);
по характеру носителя информации: молекула ДНК, длина
световой волны, бумажный либо магнитный носители;
по сфере применения: социальная, техническая, биологическая,
генетическая
по характеру источников информации: первичная, вторичная,
обобщающая и т.д.
5

6.

КОЛИЧЕСТВО ИНФОРМАЦИИ
Количеством информации называют числовую характеристику
информации, отражающую ту степень неопределенности (энтропию),
которая исчезает после получения информации
1 бит (англ. Bit – BInary digiT – двоичная цифра) – это количество
информации, при котором неопределенность уменьшается вдвое.
Частный случай: Сообщение о том, что произошло одно событие из
двух равновероятных, несет 1 бит информации
1 байт = 8 бит – основная единица измерения информации
Таблица 1 – Производные единицы информации
Единица
измерения
Краткое
обозначение
Соотношение с другими
единицами
Степень
двойки
Килобит
Кбит
1024 бита
210 бит
Мегабит
Мбит
1024 Кбита = 1 046 576 битам
220 бит
Гигабит
Гбит
1024 Мбита = 1 073 741 824 битам
230 бит
Килобайт
Кб
1024 байта
210 байт
Мегабайт
Мб
1024 Кб = 1 046 576 байтам
220 байт
Гигабайт
Гб
1024 Мб = 1 073 741 824 байтам
230 байт
6

7.

СОДЕРЖАТЕЛЬНЫЙ ПОДХОД К ИЗМЕРЕНИЮ
ИНФОРМАЦИИ
В рамках данного подхода единица измерения информации должна
быть мерой уменьшения степени его незнания.
Сообщение, уменьшающее неопределенность знаний в 2 раза несет 1
бит информации.
Частный случай: Сообщение о том, что произошло одно событие из
двух равновероятных, несет 1 бит информации.
2i = N
N – число вариантов равновероятных событий
i – количество информации в сообщении о том, что произошло одно
из N событий.
Пример: Сколько информации несет сообщение о том, что из колоды
карт достали карту красной масти?
7

8.

ОБЪЕМНЫЙ (АЛФАВИТНЫЙ) ПОДХОД К
ИЗМЕРЕНИЮ ИНФОРМАЦИИ
Алфавит – конечное множества символов, используемых для
представления информации.
Мощностью алфавита – число символов в алфавите.
2i = N (формула Хартли)
где N – мощность алфавита.
информационным весом символа.
Величину
i
можно
назвать
I = i*K
где I - количество информации во всем тексте (информационным
объемом текста),
K – количество символов в тексте.
Пример: Два текста содержат одинаковое количество символов.
Первый текст составлен в алфавите мощностью 32 символа, второй –
мощностью 64 символа. Во сколько раз отличается количество
информации в этих текстах?
8

9.

ИНФОРМАЦИОННЫЕ ПРОЦЕССЫ
Под информационным процессом принято понимать процесс,
связанный с определенными операциями над информацией, в ходе
которых может измениться содержание информации или форма ее
представления.
Принято
процессов:
различать
Сбор данных;
Передача данных;
Хранение данных;
Обработка данных.
следующие
виды
информационных
Деятельность человека, связанная с информационными
процессами называется информационной деятельностью.
9

10.

СБОР ДАННЫХ. ХРАНЕНИЕ ДАННЫХ
Поиск и хранение данных удобнее автоматизировать, когда
данные упорядочены, то есть образуют заданную структуру.
Существует три основных типа структур данных:
Линейная. Примером линейной структуры данных является
список. Каждый элемент данных в списке однозначно определяется
своим номером в массиве;
Иерархическая. В этой структуре адрес каждого элемента
определяется путем доступа (маршрутом), ведущим от вершины
структуры к данному элементу;
Табличная. В табличных структурах элементы данных
определяются адресом ячейки, который состоит из нескольких
параметров.
10

11.

ОБРАБОТКА ДАННЫХ
Осуществляется с помощью основных операций:
Формализация данных – приведение данных, поступающих из
разных источников, к единой форме;
Фильтрация данных – отсеивание «лишних»данных для
повышения их достоверности и адекватности;
Сортировка данных – упорядочение данных по заданному
признаку для повышения доступности информации;
Архивация данных – организация хранения данных в удобной
форме;
Защита данных – исключение несанкционированного доступа к
данным;
Преобразование данных – перевод данных из одной формы в
другую или из одной структуры в другую.
11

12.

ПЕРЕДАЧА ДАННЫХ
Информация передается в виде сообщений от некоторого
источника информации к ее приемнику посредством канала связи
между ними.
Схема передачи информации
Источник
сообщения
Кодирующее
устройство
Передача
информации
Декодирующее
устройство
Получатель
информации
12

13.

КОДИРОВАНИЕ ИНФОРМАЦИИ
Кодирование – это процесс преобразования сигналов или знаков
одной знаковой системы в знаки другой знаковой системы, для
использования, хранения, передачи или обработки данных. То есть это
выражение данных одного типа через данные другого типа.
Процесс
обратного
восстановления
информации
закодированного вида называется декодированием.
из
Код – это набор символов, которому приписан некоторый смысл.
Код является знаковой системой, которая содержит конечное число
символов: буквы алфавита, цифры, знаки препинания, знаки
математических операций и т.д.
Разновидностью кодирования является шифрование.
Шифр – это код, значение и правила использования которого
известны ограниченному кругу лиц.
13

14.

КОДИРОВАНИЕ ТЕКСТОВОЙ ИНФОРМАЦИИ
Кодирование заключается в том, что каждому символу ставится в
соответствие уникальный десятичный код от 0 до 255 или
соответствующий ему двоичный код от 00000000 до 11111111).
Двоичный код каждого символа занимает 1 байт памяти ЭВМ.
Этот код является порядковым номером символа
Присвоение символу конкретного кода – это соглашение, которое
фиксируется в кодовой таблице.
В первые годы развития компьютерной техники трудности
кодирования текстовой информации были связаны с отсутствием
необходимых стандартов кодирования. В настоящее время, напротив,
существующие трудности связаны с множеством одновременно
действующих и зачастую противоречивых стандартов.
14

15.

ПРИМЕРЫ КОДИРОВОК ТЕКСТОВОЙ
ИНФОРМАЦИИ
Для кодирования текстовой информации принят международный
стандарт ASCII (American Standard Code for Information Interchange).
Для кодирования русского алфавита используется несколько
кодовых таблиц:
Windows-1251 – введена компанией Microsoft с учетом широкого
распространения операционных систем и других программных
продуктов этой компании в РФ, нашла широкое распространение;
КОИ-8 (Код Обмена Информацией, восьмизначный) – другая
популярная кодировка российского алфавита, распространена в
компьютерных сетях на территории РФ и в российском секторе
Интернет;
ISO (International Standard Organization – Международный
институт стандартизации) – международный стандарт кодирования
символов русского языка. На практике используется редко.
Универсальная 16-разрядная система кодирования символов
UNICODE, применяемая с 1990-х годов, позволяет обеспечить
уникальные коды для 65536 символов, что вполне достаточно для
размещения в одной таблице символов большинства языков.
15

16.

КОДИРОВАНИЕ ГРАФИЧЕСКОЙ ИНФОРМАЦИИ
Под компьютерной (машинной) графикой
понимается
совокупность методов и приемов преобразования при помощи ЭВМ
данных в графическое представление.
Различают три вида компьютерной графики:
Растровая;
Векторная;
Фрактальная.
ЗАДАНИЕ 2
Записать
в
конспект
виды
компьютерной графики и найти
пояснения к каждому определению.
Описать достоинства и недостатки
каждого вида компьютерной графики.
16

17.

КОДИРОВАНИЕ ЗВУКОВОЙ ИНФОРМАЦИИ
Звук – это волна с непрерывно меняющейся амплитудой и
частотой. Чем больше амплитуда, тем громче звук. Чем больше
частота, тем больше тон. Частоту измеряют в Герцах. 1 Гц – это одно
колебание в секунду.
В настоящее время не существует единой стандартной системы
кодирования звуковой информации. Поэтому множество различных
компаний, которые работают в области кодирования звуковой
информации, создали свои собственные корпоративные стандарты для
звуковой информации. Но среди этих корпоративных продуктов
выделяются два основных направления:
Метод FM (Frequency Modulation – частотная модуляция)
Метод таблично-волнового синтеза
(Wave-Table)
ЗАДАНИЕ 3
Записать в конспект
основные
идеи
каждого метода.
17

18.

КОДИРОВАНИЕ ВИДЕОИНФОРМАЦИИ
Аналоговое видео – самый ранний метод передачи видеосигнала.
Композитное аналоговое видео комбинирует все видео компоненты
(яркость, цвет, синхронизацию и т.д.) в один сигнал, из-за чего
страдает качество видео.
Цифровое видео – множество технологий записи, обработки,
передачи,
хранения
и
воспроизведения
визуального
или
аудиовизуального
материала
в
цифровом
представлении.
Видеосигналы передаются в виде последовательности бит.
18

19.

КОДИРОВАНИЕ ЧИСЛОВОЙ ИНФОРМАЦИИ
Существуют два основных формата представления чисел в
памяти компьютера: целые числа и действительные числа.
В процессе кодирования целых чисел от 0 до 255 достаточно
использовать 8 разрядов двоичного кода (8 бит). Применение 16 бит
позволяет закодировать целые числа от 0 до 65 535, а с помощью 24
бит – более 16,5 миллионов различных значений.
Для того, чтобы закодировать действительные числа,
применяют 80-битное кодирование. В этом случае число
предварительно преобразовывают в нормализованную форму,
например:
3, 1427926 = 0,31427926*101;
500 000 = 0,5*106.
Первая часть закодированного числа носит название мантиссы, а
вторая часть – характеристики. Основная часть из 80 бит отводится
для хранения мантиссы, и некоторое фиксированное число разрядов
отводится для хранения характеристики.
19

20.

СИСТЕМЫ СЧИСЛЕНИЯ (СС)
Системы счисления – совокупность названий и знаков, позволяющих
записать любое число. Различают непозиционные и позиционные системы
счисления.
Особенность непозиционной СС – значение цифры не зависит от ее
положения в числе:
I
V
X
L
C
D
M
1
5
10
50
100
500
1000
Примером позиционной системы счисления является двоичная СС,
основанная на двоичном кодировании.
Двоичный (цифровой) код – это код, основанный на двоичной системе
счисления для представления буквенно-цифровых и других символов набором
комбинации цифр 1 и 0.
Преимущества двоичной системы:
Простота технической реализации (используются элементы с двумя
возможными состояниями: есть ток – нет тока, намагничен - ненамагначен);
Надежность и помехоустойчивость;
Возможность применения аппарата булевой алгебры для выполнения
логических операций;
Простота правил двоичной арифметики.
20

21.

ОСНОВНЫЕ ПОНЯТИЯ
Логика – наука, изучающая законы и формы мышления; учение о
способах рассуждений и доказательств.
Формальная логика изучает принципы умозаключений. основное
внимание уделяется не высказываниям как таковым, а отношениям между
ними.
В формальной логике вопрос «Ложны или истинны высказывания в
данной аргументации?» менее важен, чем вопрос «Правильно ли
сделан вывод в данной аргументации?»
Суждение – это форма мышления, в которой что-либо
утверждается или отрицается о предметах, признаках или их
отношениях.
Умозаключение – форма мышления, посредством которой из
одного или нескольких суждений, называемых посылками, мы по
определенным правилам вывода получаем суждение-заключение.
Высказывание – это любое предложение какого-либо языка
(утверждение), содержание которого можно определить как истинное
или ложное
21

22.

ВЫСКАЗЫВАНИЯ
Высказывание называется простым (элементарным), если никакая его
часть сама не является высказыванием.
Высказывание, состоящее из простых высказываний, называются
составным (сложным).
Простые высказывания в алгебре логики обозначаются заглавными
латинскими буквами:
А = {Аристотель - основоположник логики},
В = {На яблонях растут бананы}.
Истинному высказыванию ставится в соответствие 1, ложному - 0.
22

23.

Логическая операция КОНЪЮНКЦИЯ
В естественном языке: соответствует союзу «и»
Обозначения: &, ∧
В языках программирования обозначение: and
Иное название: логическое умножение
Конъюнкция - это логическая операция, ставящая в соответствие
каждым двум простым высказываниям составное высказывание,
являющееся истинным тогда и только тогда, когда оба исходных
высказывания истинны.
Таблица истинности конъюнкции
А
В
A&B
0
0
0
0
1
0
1
0
0
1
1
1
23

24.

Логическая операция ДИЗЪЮНКЦИЯ
В естественном языке соответствует союзу «или»
Обозначение:
В языках программирования обозначение: or
Иное название: логическое сложение
Дизъюнкция – это логическая операция, ставящая в соответствие
каждым двум простым высказываниям составное высказывание,
являющееся ложным тогда и только тогда, когда оба исходных
высказывания ложны и истинным, когда хотя бы одно из двух образующих
его высказываний истинно.
Таблица истинности дизъюнкции:
А
В
A B
0
0
0
0
1
1
1
0
1
1
1
1
24

25.

Логическая операция ИНВЕРСИЯ
В естественном языке соответствует словам «Неверно, что...» и
частице «не»
Обозначение: не А, ¬А, Ᾱ
В языках программирования обозначение: not
Иное название: отрицание
Отрицание – это логическая операция, которая каждому простому
высказыванию ставит в соответствие составное высказывание,
заключающееся в том, что исходное высказывание отрицается.
Таблица истинности отрицания:
А
Ᾱ
0
0
0
1
25

26.

Логическая операция ИНВЕРСИЯ
В естественном языке соответствует обороту «Если ..., то ...»
Обозначение:
Иное название: логическое следование
Импликация - это логическая операция, ставящая в соответствие
каждым двум простым высказываниям составное высказывание,
являющееся ложным тогда и только тогда, когда условие (первое
высказывание) истинно, а следствие (второе высказывание) ложно.
Таблица истинности импликации:
А
В
А В
0
0
1
0
1
1
1
0
0
1
1
1
26

27.

Логическая операция ЭКВИВАЛЕНЦИЯ
В естественном языке соответствует оборотам речи «Тогда и только
тогда» и «В том и только в том случае»
Обозначение: ~
Иное название: равнозначность
Эквиваленция – это логическая операция, ставящая в соответствие
каждым двум простым высказываниям составное высказывание,
являющееся истинным тогда и только тогда, когда оба исходных
высказывания одновременно истинны или одновременно ложны.
Таблица истинности эквиваленции:
А
В
А~В
0
0
1
0
1
0
1
0
0
1
1
1
27

28.

ВЫПОЛНЕНИЕ ЛОГИЧЕСКИХ ОПЕРАЦИЙ
Логические операции имеют следующий приоритет:
действия в скобках, инверсия, , , ,
Таблицу, показывающую, какие значения принимает составное
высказывание при всех сочетаниях (наборах) значений входящих в него
простых высказываний, называют таблицей истинности составного
высказывания.
Составные высказывания в алгебре логики записываются с помощью
логических выражений.
Для любого логического выражения можно построить таблицу
истинности.
28

29.

АЛГОРИТМ ПОСТРОЕНИЯ ТАБЛИЦЫ
ИСТИННОСТИ
1. Подсчитать количество переменных n в логическом выражении
2. Определить число строк в таблице m = 2n
3. Подсчитать количество логических операций в формуле
4. Установить последовательность выполнения логических операций с
учетом скобок и приоритетов
5. Определить количество столбцов в таблице: число переменных плюс
число операций
6. Выписать наборы входных переменных с учетом того, что они
представляют собой натуральный ряд n-разрядных двоичных чисел от 0
до 2n-1
7. Провести заполнение таблицы истинности по столбикам, выполняя
логические операции в соответствии с установленной в п.4
последовательностью.
29

30.

ПРАВИЛА ПЕРЕЧИСЛЕНИЯ НАБОРАВ
ВХОДНЫХ ПЕРЕМЕННЫХ
1. Определить количество наборов входных переменных
2. Разделить колонку значений первой переменной пополам и заполнить
верхнюю часть колонки 0, а нижнюю -1
3. Разделить колонку значений второй переменной на четыре части и
заполнить каждую четверть чередующимися группами 0 или 1, начиная с
группы 0
4. Продолжать деление колонок значений последующих переменных на
8, 16 и т.Д. Частей и заполнение их группами 0 или 1 до тех пор, пока
группы 0 и 1 не будут состоять из одного символа.
30

31.

ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ
Закон двойного отрицания:
не (не А) = A
Переместительный (коммутативный) закон:
для логического сложения: А B = B A
для логического умножения: A & B = B & A
Сочетательный (ассоциативный) закон:
для логического сложения: (A B) C = A (B C)
для логического умножения: (A & B) & C = A & (B & C)
Распределительный (дистрибутивный) закон:
для логического сложения: (A B) & C = (A & C) (B & C)
для логического умножения: (A & B) C = (A C)&(B C)
31

32.

ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ
Закон общей инверсии (законы де Моргана):
для логического сложения:
для логического умножения:
Закон идемпотентности:
для логического сложения: A A = A
для логического умножения: A & A = A
Законы исключения констант:
для логического сложения: A 1 = 1, A 0 = A
для логического умножения: A & 1 = A, A & 0 = 0
Закон противоречия:
A & (не A)= 0
Закон исключения третьего:
A (не A) = 1
32

33.

ЗАКОНЫ АЛГЕБРЫ ЛОГИКИ
Закон поглощения:
для логического сложения: A (A & B) = A
для логического умножения: A & (A B) = A
Закон исключения (склеивания):
для логического сложения: (A & B) (& B) = B
для логического умножения: (A B) & ( B) = B
Закон контрапозиции (правило перевертывания):
(A B) = (B A)
33