- •1. Понятие информатики
- •2. Понятие и характерные черты информации
- •Свойства информации
- •3. Виды сигнала как материального носителя информации
- •Преобразования сигнала
- •4. Системы счисления
- •5. Правила перевода чисел
- •Правила перевода целых чисел
- •Правила перевода правильных дробей
- •Правило перевода неправильных дробей
- •6. Кодирование по образцу
- •0001011101000011
- •0010 0000 0001 0010
- •2 0 1 2
- •00010100
- •Ascii-коды
- •Коды, учитывающие частоту информационных элементов
- •Коды Грея
- •7. Криптографическое кодирование
- •Метод простой подстановки
- •Метод Виженера
- •8. Эффективное кодирование
- •Универсальные методы
- •Метод Шеннона-Фано
- •Метод Хаффмена
- •9. Повышение эффективности кодирования универсальными кодами
- •Декодирование эффективных кодов
- •10. Специальные методы эффективного кодирования
- •Методы эффективного кодирования числовых последовательностей
- •2 14 18 27 34
- •2 12 4 9 7.
- •55556666888888
- •5(4)6(4)8(6),
- •Методы эффективного кодирования словарей
- •Методы эффективного кодирования естественно-языковых текстов
- •11. Помехозащитное кодирование
- •Искажение кодовых комбинаций
- •Кодовое расстояние и корректирующая способность кода
- •12. Коды, исправляющие ошибки
- •13. Измерение дискретного сигнала
- •Структурный подход к измерению информации
- •Геометрическая мера
- •Комбинаторная мера
- •Аддитивная мера
- •14. Статистический подход к измерению информации
- •Семантический подход к измерению информации
- •Полезность информации
- •Истинность информации
- •15. Структура компьютера и принципы его функционирования
- •16. Устройство управления
- •17. Арифметико-логическое устройство
- •18.Формы представления целых чисел
- •Формы представления вещественных чисел
- •Коды представления числовых данных
- •19.При сложении целых чисел последовательность шагов следующая:
- •20.Правило сложения вещественных чисел.
Правило перевода неправильных дробей
Отдельно переводится целая часть числа, отдельно – дробная. Результаты складываются.
6. Кодирование по образцу
Большинство кодов, используемых в информатике для кодирования по образцу, имеют одинаковую длину и используют двоичную систему для представления кода (и, возможно, шестнадцатеричную как средство промежуточного представления).
Прямые коды
Применяются для представления в ЭВМ числовых данных и используют двоичную систему счисления.
Выполним построение прямого кода для десятичных цифр. Вначале выпишем в таблицу десятичные цифры и их двоичные эквиваленты:
Десятичная цифра |
Двоичный эквивалент |
0 |
0 |
1 |
1 |
2 |
10 |
3 |
11 |
4 |
100 |
5 |
101 |
6 |
110 |
7 |
111 |
8 |
1000 |
9 |
1001 |
Эти коды имеют переменную длину, что неудобно для их обработки. Для получения кодов постоянной длины кодовые комбинации дополняются незначащими нулями. Тогда прямые коды постоянной длины для десятичных цифр представлены в табл. 2.2.
Таблица 2.2
Десятичные цифры |
Прямые коды |
0 |
0000 |
1 |
0001 |
2 |
0010 |
3 |
0011 |
4 |
0100 |
5 |
0101 |
6 |
0110 |
7 |
0111 |
8 |
1000 |
9 |
1001 |
Закодируем построенными кодами дискретное сообщение 1743. Для этого каждый символ сообщения заменим двоичной комбинацией из табл. 2.2. Получим:
0001011101000011
Для декодирования, он просматривается (сканируется) в направлении слева направо (т.е. в направлении его составления). Поскольку известно, что длина кодовой комбинации – 4 двоичных символа, в строке выделяются последовательно четырех символьные комбинации и каждая сопоставляется с кодовой таблицей (в нашем примере это табл. 2.2). В кодовой таблице ищется подходящая строка и выполняется замена исходным символом. Таким образом, процедура декодирования примера может быть представлена макетом:
0010 0000 0001 0010
2 0 1 2
Прямые коды могут использоваться для кодирования и нечисловых данных.
Пример 2.16. Построить двоичные коды для символов a, b, c, d.
Пронумеруем исходные символы, начиная с нуля, и по табл. 2.1 сформируем двоичные коды для номеров символов. Тогда двоичные коды исходных символов примут вид:
Исходные символы |
Номер |
Двоичный код |
a |
0 |
0 |
b |
1 |
1 |
c |
2 |
10 |
d |
3 |
11 |
Для получения двоичного кода постоянной длины добавим незначащие нули к кодовым комбинациям для a и b. Получим:
Таблица 2.3
Исходные символы |
Двоичные коды |
a |
00 |
b |
01 |
c |
10 |
d |
11 |
Закодируем полученными кодами дискретный сигнал abba. Для этого выполним замену каждого символа сигнала на соответствующую кодовую комбинацию из табл. 2.3. Получим:
00010100
Декодирование выполняется аналогично, рассмотренному выше.
Ascii-коды
Наиболее распространенным является код ASCII (American Standard Code for Information Interchange), который используется для внутреннего представления символьной информации в операционной системе MS DOS, в Блокноте операционной системы Windows’xx, а также для кодирования текстовых файлов в Интернет. Структура кода представлена ниже:
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
A |
B |
C |
D |
E |
F |
0 |
… |
… |
|
0 |
@ |
P |
` |
p |
А |
Р |
а |
… |
… |
… |
р |
Ё |
1 |
… |
… |
! |
1 |
A |
Q |
a |
q |
Б |
С |
б |
… |
… |
… |
с |
ё |
2 |
… |
… |
“ |
2 |
B |
R |
b |
r |
В |
Т |
в |
… |
… |
… |
т |
/ |
3 |
… |
… |
# |
3 |
C |
S |
c |
s |
Г |
У |
г |
… |
… |
… |
у |
\ |
4 |
… |
… |
$ |
4 |
D |
T |
d |
t |
Д |
Ф |
д |
… |
… |
… |
ф |
/ |
5 |
… |
… |
% |
5 |
E |
U |
e |
u |
Е |
Х |
е |
… |
… |
… |
х |
\ |
6 |
… |
… |
& |
6 |
F |
V |
f |
v |
Ж |
Ц |
ж |
… |
… |
… |
ц |
|
7 |
… |
… |
‘ |
7 |
G |
W |
g |
w |
З |
Ч |
з |
… |
… |
… |
ч |
|
8 |
… |
… |
( |
8 |
H |
X |
h |
x |
И |
Ш |
и |
… |
… |
… |
ш |
|
9 |
… |
… |
) |
9 |
I |
Y |
i |
y |
Й |
Щ |
й |
… |
… |
… |
щ |
|
A |
… |
… |
* |
: |
J |
Z |
j |
z |
К |
Ъ |
к |
… |
… |
… |
ъ |
|
B |
… |
… |
+ |
; |
K |
[ |
k |
{ |
Л |
Ы |
л |
… |
… |
… |
ы |
|
C |
… |
… |
, |
< |
L |
\ |
l |
| |
М |
Ь |
м |
… |
… |
… |
ь |
№ |
D |
… |
… |
- |
= |
M |
] |
m |
} |
Н |
Э |
н |
… |
… |
… |
э |
¤ |
E |
… |
… |
. |
> |
N |
^ |
n |
~ |
О |
Ю |
о |
… |
… |
… |
ю |
|
F |
… |
… |
/ |
? |
O |
_ |
o |
¤ |
П |
Я |
п |
… |
… |
… |
я |
|
Таблица кодов содержит 16 столбцов и 16 строк; каждая строка и столбец пронумерованы в шестнадцатеричной системе счисления цифрами от 0 до F. Шестнадцатеричное представление ASCII-кода складывается из номера столбца и номера строки, в которых располагается символ. Так, например, ASCII-код символа 1 есть число 3116, что по правилам перевода означает 1100012. В двоичной системе код представляется восемью разрядами, т.е. двоичный ASCII-код символа 1 есть 001100012.
Данная таблица делится на две части: столбцы с номерами от 0 до 7 составляют стандарт кода – неизменяемую часть; столбцы с номерами от 8 до F являются расширением кода и используются, в частности, для кодирования символов национальных алфавитов. В столбцах с номерами 0 и 1 находятся управляющие символы, которые используются, в частности для управления принтером. Столбцы с номерами от 2 до 7 содержат знаки препинания, арифметических действий, некоторые служебные символы, а также заглавные и строчные буквы латинского алфавита. Расширение кода включает символы псевдографики, буквы национальных алфавитов и другие символы.
В приведенной таблице ASCII-кода в качестве национального выбран русский алфавит. Пустые ячейки означают, что они не используются, а ячейки с многоточием содержат символы, которые умышленно не показаны.