Введение

Изучение дисциплины «Технологии программирования» является одним из основных моментов в процессе подготовки специалистов по разработке программного обеспечения для компьютерных систем. Это связано с тем, что первичная задача программиста заключается в применении решения о форме представления данных и выборе алгоритмов для обработки этих данных. И лишь затем выбранные структуры программы и данных реализуется на конкретном языке программирования. В связи с этим знание классических методов и приемов обработки данных позволяет избежать ошибок, которые могут возникать при чисто интуитивной разработке программ.

Так же важнейшей частью информатики как науки является теория информации, которая занимается изучением информации как таковой, ее появлением, развитием и уничтожением. К этой науке близко примыкает теория кодирования, в задачу которой входит изучение форм представления информации при ее передаче по различным каналам связи, а также при хранении и обработке.

1. Глава I Необходимые понятия и определения

Теория кодирования и теория информации возникли в начале XX века. Начало развитию этих теорий как научных дисциплин положило появление в 1948 г. статей К. Шеннона, которые заложили фундамент для дальнейших исследований в этой области.

Кодирование – способ представления информации в удобном для хранения и передачи виде. В связи с развитием информационных технологий кодирование является центральным вопросом при решении самых разных задач программирования, таких как:

• 1. представление данных произвольной структуры (числа, текст, графика) в памяти компьютера;
  2. обеспечение помехоустойчивости при передаче данных по каналам связи;
  3. сжатие информации в базах данных.

Основной моделью, которую изучает теория информации, является модель системы передачи сигналов:

Источник

Шум

Приемник

Кодер

источника

Кодер

канала

Декодер

канала

Декодер

источника

Канал

Рисунок 1 Модель системы передачи сигналов

Начальным звеном в приведенной выше модели является источник информации. Здесь рассматриваются дискретные источники без памяти, в которых выходом является последовательность символов некоторого фиксированного алфавита. Множество всех различных символов, порождаемых некоторым источником, называется алфавитом источника, а количество символов в этом множестве – размером алфавита источника. Например, можно считать, что текст на русском языке порождается источником с алфавитом из 33 русских букв, пробела и знаков препинания.

---

В более узком смысле под термином "кодирование" часто понимают переход от одной формы представления информации к другой, более удобной для хранения, передачи или обработки. Код — это набор условных обозначений (или сигналов) для записи (или передачи) некоторых заранее определенных понятий.

Для передачи в канал связи сообщения преобразуются в сигналы. Символы, при помощи которых создаются сообщения, образуют первичный алфавит, при этом каждый символ характеризуется вероятностью его появления в сообщении. Каждому сообщению однозначно соответствует сигнал, представляющий определенную последовательность элементарных дискретных символов, называемых кодовыми комбинациями. Кодирование - это преобразование сообщений в сигнал, т.е. преобразование сообщений в кодовые комбинации. Код - система соответствия между элементами сообщений и кодовыми комбинациями. Кодер - устройство, осуществляющее кодирование. Декодер - устройство, осуществляющее обратную операцию, т.е. преобразование кодовой комбинации в сообщение. Алфавит - множество возможных элементов кода, т.е. элементарных символов (кодовых символов) X = {xi}, где i = 1, 2,..., m. Количество элементов кода - m называется его основанием. Для двоичного кода xi = {0, 1} и m = 2. Конечная последовательность символов данного алфавита называется кодовой комбинацией (кодовым словом). Число элементов в кодовой комбинации – n называется значностью (длиной комбинации). Число различных кодовых комбинаций (N = mn) называется объемом или мощностью кода.

Если N0 - число сообщений источника, то N ³ N0. Множество состояний кода должно покрывать множество состояний объекта. Полный равномерный n - значный код с основанием m содержит N = mn кодовых комбинаций. Такой код называется примитивным.

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

1. Глава II Кодирование целых И действительных чисел

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

---

19:2 = 9+1

9:2 = 4+1

4:2 = 2+0

2:2 = 1

Таким образом, 1910 = 10112

Для кодирования целых чисел от 0 до 255 достаточно иметь 8 разрядов двоичного кода (8 бит). Шестнадцать бит позволяют закодировать целые числа от 0 до 65535, а 24 бита — уже более 16,5 миллионов разных значений.

Для кодирования действительных чисел используют 8-разрядное кодирование. При этом число предварительно преобразуется в нормализованную форму:

3,1415926 = 0,31415926 × 101

300 000 = 0,3 × 106

123 456 789 = 0,123456789 × 1010

Первая часть числа называется мантиссой, а вторая — характеристикой. Большую часть из 8 бит отводят для хранения мантиссы (вместе со знаком) и некоторое фиксированное количество разрядов отводят для хранения характеристики (тоже со знаком).

Для того, чтобы записать в памяти ЭВМ действительное число, сначала его необходимо преобразовать в экспоненциальную форму. Посмотрим на примере, как это происходит.

Возьмем действительное число 184,525. В информатике принято отделять целую часть от дробной не десятичной запятой, а точкой. В соответствии с этим правилом, перепишем: 184.525.

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

0.184525Е+3,

где 184525 — мантисса, 3 — порядок, Е заменяет десятичное основание степени.

Действительное число может быть как положительным, так и отрицательным. Значит, в экспоненциальном виде и мантисса, и порядок могут иметь как положительные, так и отрицательные знаки. Поэтому, при записи действительного числа в память ЭВМ, это необходимо учитывать.

Таким образом, в общем виде экспоненциальная форма записи действительного числа имеет следующий вид:

± 0.ХХХХХЕ ± XX.

Такая форма записи позволяет увидеть, что мантисса и порядок отделены друг от друга. Поэтому хранить их в памяти ЭВМ можно отдельно друг от друга.

Кодирование буквенно-цифровой и символьной информации

Помимо целых и действительных чисел, в памяти ЭВМ находится буквенно-цифровая и символьная информация, посредством которой формируются тексты различного содержания. Это могут быть буквы латинского, русского или какого-либо другого алфавита, цифры (не путать с числами!), формулы, а также различные другие символы.

Обратимся к тому факту, что один байт состоит из восьми битов. Это означает, что количество возможных комбинаций, состоящих из восьми нулей и единиц, составляет 28=256. Это, в свою очередь, обозначает возможность закодировать 256 различных символов.

---

Такого количества оказывается достаточно, чтобы закодировать буквы латинского алфавита — их всего 52 буквы (26 строчных и 26 заглавных); десятичные цифры 0....9; знаки препинания; арифметические знаки и другие символы.

Информация называется закодированной, если каждая ее элементарная частица представлена в виде двоичного кода.

Если в печатной продукции текстовая информация представляет собой набор напечатанных букв, то в памяти ЭВМ информация представлена в виде последовательности кодов букв. Иначе говоря, вместо каждой буквы текста хранится ее номер кода. И только при выводе на внешние устройства, например, дисплей или принтер, происходит формирование изображения привычных нашему восприятию букв в соответствии с их кодами.

Существует несколько вариантов кодировки. Наиболее распространенным считается ASCII (American national Standard Code for Information Interchange), что переводится на русский как американский стандартный код обмена информацией. В качестве примера приведем коды нескольких букв латинского алфавита:

А 01000001, а 01100001,

В 01000010, b 01100010,

С 01000011, с 01100011;

десятичных цифр:

0 00110000,

1 00110001,

2 00110010,

Существуют и другие, менее распространенные кодировки, такие как, КОИ-7 (код обмена информацией, семизначный), КОИ-8 (код обмена информации, восьмизначный), кодировка символов русского языка — Windows-1251 и UNICODE — универсальная, основанная на 16-разрядном кодировании символов.

1. Глава III Некоторые теоремы ПОБУКВЕННОГО кодирования

В этом параграфе приведены некоторые теоремы о свойствах побуквенного кодирования.

Пусть даны алфавит источника , кодовый алфавит . Обозначим множество всевозможных последовательностей в алфавите А (В). Множество всех сообщений в алфавите А обозначим S. Кодирование может сопоставлять код всему сообщению из множества S как единому целому или строить код сообщения из кодов его частей (побуквенное кодирование).

Побуквенное кодирование задается таблицей кодовых слов: , , . Множество кодовых слов V={β_i} называется множеством элементарных кодов. Используя побуквенное кодирование, можно закодировать любое сообщение следующим образом , т.е. общий код сообщения складывается из элементарных кодов символов входного алфавита.

---

Количество букв в слове α=α₁…α_k называется длиной слова. (Обозначение |α|=k) Пустое слово, т.е. слово, не содержащее ни одного символа обозначается Λ. Если α=α₁α₂, то α₁ – начало (префикс) слова α, α₂ – окончание (постфикс) слова α.

Побуквенный код называется разделимым (или однозначно декодируемым), если любое сообщение из символов алфавита источника, закодированное этим кодом, может быть однозначно декодировано, т.е. если β_i1 …β_ik=β_j1…β_jt, то k=t и при любых s=1,…,k i_s=j_s. При разделимом кодировании любое кодовое слово единственным образом разлагается на элементарные коды.

Побуквенное кодирование задается таблицей кодовых слов: , ,. Множество кодовых словV={βi} называется множеством элементарных кодов. Используя побуквенное кодирование, можно закодировать любое сообщение следующим образом, т.е. общий код сообщения складывается из элементарных кодов символов входного алфавита.

Количество букв в слове α=α1…αk называется длиной слова. (Обозначение |α|=k) Пустое слово, т.е. слово, не содержащее ни одного символа обозначается Λ. Если α=α1α2, то α1 – начало (префикс) слова α, α2 – окончание (постфикс) слова α.

Побуквенный код называется разделимым (или однозначно декодируемым), если любое сообщение из символов алфавита источника, закодированное этим кодом, может быть однозначно декодировано, т.е. если βi1 …βik=βj1…βjt , то k=t и при любых s=1,…,k is=js . При разделимом кодировании любое кодовое слово единственным образом разлагается на элементарные коды.

1. Глава IV оптимальное ПОБУКВЕННОЕ кодирование

   1. Основные понятия

При кодировании сообщений считается, что символы сообщения порождаются некоторым источником информации. Источник считается заданным полностью, если дано вероятностное описание процесса появления сообщений на выходе источника. Это означает, что в любой момент времени определена вероятность порождения источником любой последовательности символов Р(x₁x₂x₃...x_L), L≥1. Такой источник называется дискретным вероятностным источником.

Если вероятностный источник с алфавитом А={a₁, a₂, ..., a_n} порождает символы алфавита независимо друг от друга, т.е. знание предшествующих символов не влияет на вероятность последующих, то такой источник называется бернуллиевским. Тогда для любой последовательности x₁x₂...x_L, L≥1, порождаемой источником, выполняется равенство:

---

Смотрите также файлы

• Особенности семейного воспитания(Семья – основа семейного воспитания).pdf

• Тенденции развития международной валютной системы ( Понятие и сущность международной валютной системы).pdf

• Социальное страхование и его функции (Проблемы и перспективы развития).pdf

• Государственная служба в Российской Федерации: опыт, современное состояние и направления совершенствования (История и опыт государственной службы в Российской Федерации ).pdf

• Основные направления реформы государственной службы в России (Система государственной службы ).pdf