Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Кодирование информации в ЭВМ - одна из задач теории кодирования.
Теория кодирования - один из разделов теоретической информатики. Одна из задач - разработка принципов наиболее экономичного кодирования. Эта задача касается передачи, обработки, хранения информации. Частное ее решение – представление информации в компьютере.
Алфавит, в котором источник информации представляет сообщение, называется первичным.
Алфавит, в котором представлено сообщение после обработки в кодирующем устройстве, называется вторичным.
Код – это соответствие знаков первичного алфавита знакам вторичного алфавита.
Кодирование – перевод сообщения из первичного алфавита во вторичный.
Декодирование – операция обратная кодированию.
Операции кодирования и декодирования называются обратимыми, если их последовательное применение обеспечит возврат к исходной информации без каких-либо ее потерь.
Пример обратимого: слова ↔ телеграфный код.
необратимого: английский ↔ русский – здесь неоднозначно.
Математическая постановка условия обратимого кодирования.
Пусть
первичный алфавит А сост. из N знаков со средней информацией на знак IА
вторичный В – из М знаков со средней информацией на знак I В.
Пусть сообщение в первичном алфавите содержит n знаков, а закодированное – m знаков. Если исходное сообщение содержит IS (A) информации, а закодированное If (B), то условие обратимости кодирования (то есть неисчезновения информации при кодировании) очевидно может быть записано так:
IS (A) ≤ If (B) - то есть операция обратимого кодирования может увеличить количество информации в сообщении, но не может уменьшить ее.
n* I (A) ≤ m* I (B) (заменили произведением числа знаков на среднее
информационное содержание знака).
Среднее число знаков вторичного алфавита, который используется для кодирования одного знака первичного назовем длиной кода.
К (А, В)=m/n
К (А, В)≥ I (A) / I (B)
Минимально возможная длина кода: Кmin (А, В)= I (A) / I (B) –это нижний предел длины кода.
Первая теорема Шеннона.
При отсутствии помех всегда возможен такой вариант кодирования сообщения, при котором средняя длина кода будет сколь угодно близкой к отношению средних информаций на знак первичного и вторичного алфавитов.
Для двоичного кода М=2.
Кmin (А, В)= I (A) / log2 M= I (A) , здесь I (A) - средняя информация на знак первичного алфавита.
Первая теорема Шеннона (переформулировка).
При отсутствии помех средняя длина двоичного кода может быть сколь угодно близкой к средней информации, приходящейся на знак первичного алфавита.
Какие же могут быть особенности вторичного алфавита при кодировании:
Длина кода может быть одинаковой для всех знаков первичного алфавита (код равномерный) или различной (неравномерный код)
Коды могут строиться для отдельного знака первичного алфавита (алфавитное кодирование) или для их комбинаций (кодирование блоков, слов).
Равномерное алфавитное кодирование.
Пример его использования – представление символьной информации в компьютере.
Определим, какой должна быть длинна кода:
Компьютерный алфавит С включает 52 буквы латинского алфавита
· 66 букв русского (прописные и строчные)
· Цифры 0…9 – 10 штук
· Знаки математических операций, препинания, спецсимволы – 20 шт.
Итого-148 символов.
К (С, 2) ≥ log2 148 ≥ 7,21, но длина кода – целое число, следовательно, К (С,2) =8. Именно такой способ кодирования принят в компьютерных системах. Называют 8 бит=1 байт, а кодирование байтовым
Один байт соответствует количеству информации в одном знаке алфавита при их равновероятном распределении. Это объемный (знакомый уже) способ измерения информации.
Итак. Символы (characters) в компьютере хранятся в виде числового кода, причем каждому символу ставиться в соответствии своя уникальная комбинация двоичных разрядов. В этом случае текст будет представлен как длинный ряд битов, в котором следующее друг за другом комбинации битов отражают последовательность символов в исходном тексте. Присвоение символу конкретного двоичного кода _ это вопрос соглашения, которое фиксируется в кодовой таблице – их существует несколько.
Таблица, в которой устанавливается однозначное соответствие между символами и их порядковыми номерами, называется таблицей кодировки.
Для разных типов ЭВМ используют различные таблицы кодировки.
С распространением ПК типа IBM PC международным стандартом стала таблица кодировки под названием American Standard Cod for Information Interchange – ASCII.
Системы кодирования текстовых данных были разработаны и в других странах. Так, например, в СССР в этой области действовала система кодирования КОИ-7 и КОИ-8.
Система, основанная на 16-разрядном кодировании символов, получила название универсальной Unicode. Шестнадцать разрядов позволяют обеспечить уникальные коды для 65536 различных символов – этого поля достаточно для размещения в одной таблице символов большинства языков планеты.
ЧИСЛО имеет ЗНАЧЕНИЕ и ФОРМУ ПРЕСТАВЛЕНИЯ. Последняя определяет порядок записи числа с помощью предназначенных ля этого знаков. При этом ЗНАЧЕНИЕ является инвариантом, то есть не зависит от способа его представления.
Системой счисления называется совокупность приемов наименования и записи чисел.
В любой системе счисления для представления чисел выбираются некоторые базовые символы (цифры), и все числа получаются в результате строго определенных операций над ними. Число таких базовых символов называется основанием системы счисления.
Существует два известных типа систем счисления: непозиционные и позиционные.
В непозиционных системах счисления каждая цифра имеет одно и тоже значение независимо от положения в записи числа (значение знака не зависит от того места, которое он занимает в числе).
Непозиционной системой счисления является самая простая система с одним символом (палочкой). Для изображения какого-либо числа в этой системе надо записать количество палочек, рав ное данному числу. Например, запись числа 12 в такой системе счисления будет иметь вид: 111111111111, где каждая «палочка» обозначена символом 1. Эта система неэффективна, так как фор ма записи очень громоздка.
К непозиционной системе счисления относится и римская, сим волы алфавита которой и обозначаемое ими количество представ лены в табл. 1.
Таблица 1
|
Римские цифры |
I |
V |
X |
L |
С |
О |
м |
|
Значение (обозначаемое количество) |
1 |
5 |
10 |
50 |
100 |
500 |
1000 |
В общем случае непозиционные системы счисления характери зуются сложными способами записи чисел и правилами выполнения арифметических операций.
В настоящее время наиболее распространены позиционные системы счисления. Все обрабатываемые данные в персональных компьютерах представлены в виде кодов и чисел в позиционной системе счисления.
Конкретное значение числа в позиционной системе определяется не только самими его цифрами, но и местоположением каждой из цифр, т.е. цифры имеют разный вес в записи числа. Примером такой системы счисления является привычная нам десятичная система счисления. Эта система использует десять базовых символов (цифр): 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. В позиционной системе счисления число может быть представлено в виде суммы произведений коэффициентов на степени основания системы счисления. Например, число 1909 можно представить в виде многочлена по степеням основания:
1*103 + 9*102 + 0101 + 9*100
Основание системы счисления может быть отличным от 10. Запись произвольного числа X в системе счисления по основанию R имеет вид:
X = an*Rn + an-1 *Rn-1 + ... + a1 *R1 + a0 *R0, а цифры ai принадлежат 0, ... , R-1.
В компьютерных науках используется несколько позиционных систем счисления: двоичная, восьмеричная, шестнадцатеричная системы счисления.
Двоичная система счисления
Особая значимость двоичной системы счисления в информатике определяется тем, что внутренне представление любой информации в компьютере является двоичным, то есть описываемым наборами только из двух знаков – 0 и 1. Цифра двоичной системы счисления хранится в элементарной ячейке памяти, называемой битом. Бит – это наименьшая единица измерения количества информации, известная в природе (да - нет).
Восемь бит обеспечивают основу для двоичной арифметики и для представления символов в памяти компьютера. Восемь бит дают 256 различных комбинаций включенных и выключенных состояний: от "все выключены" (00000000) до "все включены" (11111111). По соглашению биты в байте пронумерованы от 0 до 7 справа налево, как это показано в таблице:
|
Номера битов: |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
0 |
|
Значения битов: |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
Двоичная система счисления является позиционной, а соответственно значение двоичного числа определяется позицией каждого бита. В общем виде число в двоичной системе счисления представляется в форме:
X = an*2n + an-1 *2n-1 + ... + a1 *21 + a0 *20 ai принадлежат 0, 1
Двоичное число не ограничивается только восьмью битами. В зависимости от архитектуры компьютера, он оперируют 16-битными, 32-битными, 64-битными представлениями чисел. Правила арифметики во всех позиционных системах одинаковы.
Таблица сложения в двоичной системе счисления имеет вид:
|
0 |
+ |
0 |
= |
0 |
|
0 |
+ |
1 |
= |
1 |
|
1 |
+ |
0 |
= |
1 |
|
1 |
+ |
1 |
= |
10 |
При сложении осуществляется перенос избытка из одного столбца в другой.
Таблица умножения в двоичной системе счисления имеет вид:
|
0 |
х |
0 |
= |
0 |
|
0 |
х |
1 |
= |
0 |
|
1 |
х |
0 |
= |
0 |
|
1 |
х |
1 |
= |
1 |
Замечание: если справа приписать 0, то двоичное число удваивается, а в 10-ой удесятеряется, а в 16-ой ушестнадцатиряется.
Восьмеричная система счисления
Для более удобного представления двоичных данных также используется система счисления с основанием восемь (восьмеричная система счисления). В восьмеричной системе счисления используется восемь цифр: 0,1,2,3,4,5,6,7.
Шестнадцатеричная система счисления
Для "стенографического" представления двоичных чисел используется система счисления с основанием 16 (шестнадцатеричная система счисления). В шестнадцатеричной системе счисления используется шестнадцать цифр: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F.
Примем без доказательства следующие правила перевода целых чисел из одной системы счисления в другую.
Правило 1. Перевод числа x из системы счисления основанием P в систему счисления с основанием Q заключается в последовательном нахождении остатков от деления числа x на основание Q, при этом процесс продолжается до тех пор, пока частное от деления не будет меньше основания Q. Все вычисления выполняются в системе счисления с основанием P, т.е. основание Q должно также быть выражено в системе счисления с основанием P. Остатки от деления должны быть выражены цифрами системы счисления с основанием R. Представление искомого числа в системе счисления с основанием R получается выписыванием последнего частного и остатков от деления в обратном порядке.
На практике такой порядок перевода чисел используется при переводе из десятичной системы счисления в восьмеричную, шестнадцатеричную и двоичную.
57410=?8=10768 574 8
56 71 8
14 67 8 8
8 7 8 1
6 0
57410=?16=23Е16
574 16
48 35 16
94 32 2
80 3
14
Правило 2. Перевод числа x из системы счисления основанием P в систему счисления с основанием Q осуществляется путем представления числа х по степеням основания P. Все вычисления выполняются в системе счисления с основанием Q, т. е. основание P и цифры исходного числа должны также быть выражены в системе счисления с основанием Q. На практике такой порядок перевода чисел используется при переводе из двоичной, восьмеричной и шестнадцатеричной системы счисления в десятичную.
23Е16 =?10: = 2*162+3*161+ Е*160=2*162+3*161+14*160=57410
10788=1*83+0*82+7*81+6*80=57410