Кодирование и декодирование информации:
· кодирование – это перевод информации с одного языка на другой (запись в другой системе символов, в другом алфавите)
· обычно кодированием называют перевод информации с «человеческого» языка на формальный, например, в двоичный код, а декодированием – обратный переход
· один символ исходного сообщения может заменяться одним символом нового кода или несколькими символами, а может быть и наоборот – несколько символов исходного сообщения заменяются одним символом в новом коде (китайские иероглифы обозначают целые слова и понятия)
·
кодирование может быть равномерное и неравномерное;
при равномерном кодировании все символы кодируются кодами равной длины;
при неравномерном кодировании разные символы могут кодироваться кодами разной
длины, это затрудняет декодирование
· закодированное сообщение можно однозначно декодировать с начала, если выполняется условие Фано: никакое кодовое слово не является началом другого кодового слова;
· закодированное сообщение можно однозначно декодировать с конца, если выполняется обратное условие Фано: никакое кодовое слово не является окончанием другого кодового слова;
· условие Фано – это достаточное, но не необходимое условие однозначного декодирования.
Двоичная система:
· четные числа оканчиваются на 0, нечетные – на 1;
· числа, которые делятся на 4, оканчиваются на 00, и т.д.; числа, которые делятся на 2k, оканчиваются на k нулей
· если число N принадлежит интервалу 2k-1 £ N < 2k, в его двоичной записи будет всего k цифр, например, для числа 125:
26 = 64 £ 125 < 128 = 27, 125 = 11111012 (7 цифр)
· числа вида 2k записываются в двоичной системе как единица и k нулей, например:
16 = 24 = 100002
· числа вида 2k-1 записываются в двоичной системе k единиц, например:
15 = 24-1 = 11112
если известна двоичная запись числа N, то двоичную запись
числа 2·N можно легко получить, приписав в конец ноль, например:
15 = 11112, 30 = 111102, 60 = 1111002, 120 = 11110002
· отрицательные целые числа хранятся в памяти в двоичном дополнительном коде (подробнее см. презентацию «Компьютер изнутри»)
· для перевода отрицательного числа (-a) в двоичный дополнительный код нужно сделать следующие операции:
o перевести число a-1 в двоичную систему счисления;
o сделать инверсию битов: заменить все нули на единицы и единицы на нули в пределах разрядной сетки (см. пример Р-00 далее).
Построение и анализ таблиц истинности логических выражений:
· условные обозначения логических операций
¬ A, не A (отрицание, инверсия)
A Ù B, A и B (логическое умножение, конъюнкция)
A Ú B, A или B (логическое сложение, дизъюнкция)
A → B импликация (следование)
A º B эквивалентность (равносильность)
· операцию «импликация» можно выразить через «ИЛИ» и «НЕ»:
A → B = ¬ A Ú B или в других обозначениях A → B =
· иногда для упрощения выражений полезны формулы де Моргана:
¬ (A Ù B) = ¬ A Ú ¬ B
¬ (A Ú B) = ¬ A Ù ¬ B
· если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», «импликация», и самая последняя – «эквивалентность»
· таблица истинности выражения определяет его значения при всех возможных комбинациях исходных данных
· если известна только часть таблицы истинности, соответствующее логическое выражение однозначно определить нельзя, поскольку частичной таблице могут соответствовать несколько разных логических выражений (не совпадающих для других вариантов входных данных);
· количество разных логических выражений, удовлетворяющих неполной таблице истинности, равно , где – число отсутствующих строк; например, полная таблица истинности выражения с тремя переменными содержит 23=8 строчек, если заданы только 6 из них, то можно найти 28-6=22=4 разных логических выражения, удовлетворяющие этим 6 строчкам (но отличающиеся в двух оставшихся)
· логическая сумма A + B + C + … равна 0 (выражение ложно) тогда и только тогда, когда все слагаемые одновременно равны нулю, а в остальных случаях равна 1 (выражение истинно)
· логическое произведение A · B · C · … равно 1 (выражение истинно) тогда и только тогда, когда все сомножители одновременно равны единице, а в остальных случаях равно 0 (выражение ложно)
· логическое следование (импликация) А→В равна 0 тогда и только тогда, когда A (посылка) истинна, а B (следствие) ложно
· эквивалентность АºB равна 1 тогда и только тогда, когда оба значения одновременно равны 0 или одновременно равны 1.
Источник: inf-ege.sdamgia.ru