Здесь можно найти учебные материалы, которые помогут вам в написании курсовых работ, дипломов, контрольных работ и рефератов. Так же вы мажете самостоятельно повысить уникальность своей работы для прохождения проверки на плагиат всего за несколько минут.
Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение оригинальности любого файла в формате MS Word. После такого повышения оригинальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, РУКОНТЕКСТ, etxt.ru. Программа «StudentHelp» работает по уникальной технологии так, что на внешний вид, файл с повышенной оригинальностью не отличается от исходного.
Результат поиска
Наименование:
реферат Кодирование информации. Кодирование чисел, текста, изображения и звука
Информация:
Тип работы: реферат.
Добавлен: 12.10.2012.
Год: 2010.
Страниц: 7.
Уникальность по antiplagiat.ru: < 30%
Описание (план):
В
случае использования неравномерного
кодирования или сигналов разной
длительности (ситуации (2), (3) и (4)) для отделения
кода одного знака от другого между ними
необходимо передавать специальный сигнал
– временной разделитель (признак конца
знака) или применять такие коды, которые
оказываются уникальными, т.е. несовпадающими
с частями других кодов. При равномерном
кодировании одинаковыми по длительности
сигналами (ситуация (1)) передачи специального
разделителя не требуется, поскольку отделение
одного кода от другого производится по
общей длительности, которая для всех
кодов оказывается одинаковой (или одинаковому
числу бит при хранении).
Длительность
двоичного элементарного импульса
показывает, сколько времени требуется
для передачи 1 бит информации. Очевидно,
для передачи информации, в среднем
приходящейся на знак первичного алфавита,
необходимо время. Таким образом, задачу
оптимизации кодирования можно сформулировать
в иных терминах: построить такую систему
кодирования, чтобы суммарная длительность
кодов при передаче (или суммарное число
кодов при хранении) данного сообщения
была бы наименьшей.
Если
имеется источник информации с энтропией
Н(х) и канал связи с пропускной
способностью С, то если С > H(X), то всегда
можно закодировать достаточно длинное
сообщение таким образом, что оно будет
передано без задержек. Если же, напротив,
С < H(X), то передача информации без задержек
невозможна.
Первая
теорема Шеннона декларирует возможность
создания системы эффективного кодирования
дискретных сообщений, у которой среднее
количество двоичных символов на один
символ сообщения асимптотически стремится
к энтропии источника сообщений (в отсутствии
помех).
Первая
теорема Шеннона (переформулировка).
При
отсутствии помех средняя длина
двоичного кода может быть сколь
угодно близкой к средней информации,
приходящейся на знак первичного алфавита.
Какие
же могут быть особенности вторичного
алфавита при кодировании:
Элементарные
коды 0 и 1 могут иметь одинаковые
длительности (t0=t1) или разные (?).
Длина
кода может быть одинаковой для всех знаков
первичного алфавита (код равномерный)
или различной (неравномерный код)
Коды
могут строиться для отдельного
знака первичного алфавита (алфавитное
кодирование) или для их комбинаций
(кодирование блоков, слов).
3. Вторая
теорема Шеннона
О
тношение
пропускной способности канала связи
к скорости неискаженной передачи символов
алфавита передаваемого сообщения должно
быть больше или равно энтропии передачи
одного символа.
Вторая
теорема Шеннона гласит, что при
наличии помех в канале всегда
можно найти такую систему
кодирования, при которой сообщения
будут переданы с заданной достоверностью.
При наличии ограничения пропускная способность
канала должна превышать производительность
источника сообщений. Вторая теорема Шеннона
устанавливает принципы помехоустойчивого
кодирования. Для дискретного канала с
помехами теорема утверждает, что, если
скорость создания сообщений меньше или
равна пропускной способности канала,
то существует код, обеспечивающий передачу
со сколь угодно малой частотой ошибок.
Доказательство
теоремы основывается на следующих
рассуждениях. Первоначально последовательность
X={xi} кодируется символами из В так,
что достигается максимальная пропускная
способность (канал не имеет помех). Затем
в последовательность из В длины n вводится
r символов по каналу передается новая
последовательность из n + r символов. Число
возможных последовательностей длины
n + r больше числа возможных последовательностей
длины n. Множество всех последовательностей
длины n + r может быть разбито на n подмножеств,
каждому из которых сопоставлена одна
из последовательностей длины n. При наличии
помехи на последовательность из n + r выводит
ее из соответствующего подмножества
с вероятностью сколь угодно малой.
Теорема
позволяет определять на приемной стороне
канала, какому подмножеству принадлежит
искаженная помехами принятая последовательность
n + r, и тем самым восстановить исходную
последовательность длины n.
Эта
теорема не дает конкретного метода
построения кода, но указывает на пределы
достижимого в области помехоустойчивого
кодирования, стимулирует поиск
новых путей решения этой проблемы.
4. Способы
представления кодов
В
зависимости
от применяемых методов кодирования,
используют различные математические
модели кодов, при этом наиболее
часто применяется представление
кодов в виде: кодовых матриц;
кодовых деревьев; многочленов; геометрических
фигур и т.д.
4.1
Матричное представление
кодов
Используется
для представления равномерных
n - значных кодов. Для примитивного (полного
и равномерного) кода матрица содержит
n - столбцов и 2n -
строк, т.е. код использует все сочетания.
Для помехоустойчивых (корректирующих,
обнаруживающих и исправляющих ошибки)
матрица содержит n - столбцов (n =
k+m, где k-число информационных, а
m - число проверочных разрядов) и 2k
- строк (где 2k -
число разрешенных кодовых комбинаций).
При больших значениях n и k матрица
будет слишком громоздкой, при этом код
записывается в сокращенном виде. Матричное
представление кодов используется, например,
в линейных групповых кодах, кодах Хэмминга
и т.д.
4.2
Представление кодов
в виде кодовых деревьев
Кодовое
дерево - связной граф, не содержащий
циклов. Связной
граф - граф, в котором для любой пары
вершин существует путь, соединяющий эти
вершины. Граф состоит из узлов (вершин)
и ребер (ветвей), соединяющих узлы, расположенные
на разных уровнях. Для построения дерева
равномерного двоичного кода выбирают
вершину называемую корнем дерева (истоком)
и из нее проводят ребра в следующие две
вершины и т.д.
Пример
кодового дерева для полного кода
приведен на рис.1.
1
0
1
0
1
0
1 0
1 0
1 0
1
0
111 110
101 100
011
010 001
000
Рис.1.
Дерево для полного двоичного
кода при n = 3
Дерево
помехоустойчивого кода строится на
основе дерева полного кода путем
вычеркивания запрещенных кодовых
комбинаций. Для дерева неравномерного
кода используется взвешенный граф, при
этом на ребрах дерева указываются вероятность
переходов. Представление кода в виде
кодового дерева используется, например,
в кодах Хаффмена.
4.3
Представление кодов
в виде многочленов
Представление
кодов в виде полиномов основано на подобии
(изоморфизме) пространства двоичных
n - последовательностей и пространства
полиномов степени не выше n - 1.
Код
для любой системы счисления
с основанием Х может быть представлен
в виде:
G
(x) = an-1 xn-1+ an-2 xn-2+...
+ a1 x+ a0 =,
где
аi -
цифры данной системы счисления (в двоичной
0 и 1); х
- символическая (фиктивная) переменная,
показатель степени которой соответствует
номерам разрядов двоичного числа-
Например:
Кодовая комбинация 1010110 может быть
представлена в виде:
G
(x) =1?x6+0?x5+1?x4+0?x3+1?x2+1?x1+0?x0
=x6+x4+x2+x=10101
При
этом операции над кодами эквивалентны
операциям над многочленами. Представление
кодов в виде полиномов используется
например, в циклических кодах.
4.4
Геометрическое представление
кодов
Любая
комбинация n - разрядного двоичного
кода может быть представлена как вершина
n - мерного единичного куба, т.е. куба
с длиной ребра равной 1. Для двухэлементного
кода (n = 2) кодовые комбинации располагаются
в вершинах квадрата. Для трехэлементного
кода
(n
= 3) - в вершинах единичного куба (рис.2).
В
общем случае n мерный куб имеет
2nвершин, что соответствует
набору кодовых комбинаций 2n.
n
= 2 n = 3
Рис.2.
Геометрическая модель двоичного кода
Геометрическая
интерпретация кодового
расстояния. Кодовое расстояние - минимальное
число ребер, которое необходимо пройти,
чтобы попасть из одной кодовой комбинации
в другую. Кодовое расстояние характеризует
помехоустойчивость кода.
5. Международные
системы байтового кодирования.
И
нформатика
и ее приложения интернациональны.
Это связано как с объективными
потребностями человечества в единых
правилах и законах хранения, передачи
и обработки информации, так и с тем, что
в этой сфере деятельности (особенно в
ее прикладной части) заметен приоритет
одной страны, которая благодаря этому
получает возможность «диктовать моду».
Компьютер
считают универсальным преобразователем
информации. Тексты на естественных языках
и числа, математические и специальные
символы - одним словом все, что в быту
или в профессиональной деятельности
может быть необходимо человеку, должно
иметь возможность быть введенным в компьютер.
В
силу безусловного приоритета двоичной
системы счисления при внутреннем
представлении информации в компьютере
кодирование «внешних» символов основывается
на сопоставлении каждому из них определенной
группы двоичных знаков. При этом из технических
соображений и из соображений удобства
кодирования-декодир вания следует пользоваться
равномерными кодами, т.е. двоичными группами
равной длины.
Попробуем
подсчитать наиболее короткую длину
такой комбинации с точки зрения
человека, заинтересованного в использовании
лишь одного естественного алфавита -
скажем, английского: 26 букв следует умножить
на 2 (прописные и строчные) - итого 52; 10
цифр, будем считать, 10 знаков препинания;
10 разделительных знаков (три вида скобок,
пробел и др.), знаки привычных математических
действий, несколько специальных символов
(типа #, $, & и др.) — итого ~ 100. Точный подсчет
здесь не нужен, поскольку нам предстоит
решить простейшую задачу: имея, скажем,
равномерный код из групп по N двоичных
знаков, сколько можно образовать разных
кодовых комбинаций. Ответ очевиден К
= 2N. Итак, при N = 6 К = 64 - явно мало, при N =
7 К = 128 - вполне достаточно.
Однако,
для кодирования нескольких (хотя
бы двух) естественных алфавитов (плюс
все отмеченные выше знаки) и этого
недостаточно. Минимально достаточное
значение N в этом случае 8; имея 256 комбинаций
двоичных символов, вполне можно решить
указанную задачу. Поскольку 8 двоичных
символов составляют 1 байт, то говорят
о системах «байтового» кодирования.
Наиболее
распространены две такие системы: EBCDIC
(Extended Binary Coded Decimal Interchange Code) и ASCII (American
Standard Information Interchange).
Первая
- исторически тяготеет к «большим»
машинам, вторая чаще используется на
мини- и микро-ЭВМ (включая персональные
компьютеры). Ознакомимся подробнее
именно с ASCII, созданной в 1963 г.
В
своей первоначальной версии это - система
семибитного кодирования. Она ограничивалась
одним естественным алфавитом (английским),
цифрами и набором различных символов,
включая «символы пишущей машинки» (привычные
знаки препинания, знаки математических
действий и др.) и «управляющие символы».
Примеры последних легко найти на клавиатуре
компьютера: для микро-ЭВМ, например, DEL
- знак удаления символа.
В
следующей версии фирма IBM перешла
на расширенную 8-битную кодировку. В
ней первые 128 символов совпадают
с исходными и имеют коды со
старшим битом равным нулю, а остальные
коды отданы под буквы некоторых европейских
языков, в основе которых лежит латиница,
греческие буквы, математические символы
(скажем, знак квадратного корня) и символы
псевдографики. С помощью последних можно
создавать таблицы, несложные схемы и
др.
Для
представления букв русского языка
(кириллицы) в рамках ASCII было предложено
несколько версий. Первоначально был разработан
ГОСТ под названием КОИ-7, оказавшийся
по ряду причин крайне неудачным; ныне
он практически не используется.
В
табл. 1.9 приведена часто используемая
в нашей стране модифицированная альтернативная
кодировка. В левую часть входят исходные
коды ASCII; в правую часть (расширение ASCII)
вставлены буквы кириллицы взамен букв,
немецкого, французского алфавитов (не
совпадающих по написанию с английскими),
греческих букв, некоторых спецсимволов.
Знакам
алфавита ПЭВМ ставятся в соответствие
шестнадцатиричные числа по правилу:
первая - номер столбца, вторая - номер
строки. Например: английская 'А' - код 41,
русская 'и' - код А8.
Таблица
1.9
Таблица
кодов ASCII (расширенная)
Одним
из достоинств этой системы кодировки
русских букв является их естественное
упорядочение, т.е. номера букв следуют
друг за другом в том же порядке, в каком
сами буквы стоят в русском алфавите. Это
очень существенно при решении ряда задач
обработки текстов, когда требуется выполнить
или использовать лексикографическое
упорядочение слов.
Из
сказанного выше следует, что даже 8-битная
кодировка недостаточна для кодирования
всех символов, которые хотелось бы
иметь в расширенном алфавите. Все
препятствия могут быть сняты при переходе
на 16-битную кодировку Unicode, допускающую
65536 кодовых комбинаций. и т.д.................
