Файл: "Методы кодирования данных. Пример".pdf

ВУЗ: Не указан

Категория: Курсовая работа

Дисциплина: Не указана

Добавлен: 27.06.2023

Просмотров: 12

Скачиваний: 2

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

Пример

a1 1000 111 011 Необходимо закодировать

a0 0100 110 101информационную комбинацию:

a31 0010 101 110 1011

a41 0001 011 111

Полученное значение проверочных

1011 001 разрядов.

В общем случае: a1, a2, a3, a4 – информационная кодовая комбинация в общем виде:

a1 a2 a3 a4 b1 b2 bb= a1 a aДля заданной образующей матрицы

b2 = a1 a a4

b= a1 a a4

В самом общем случае алгоритм образования проверочных символов b1…b2 по известной информационной частиa1, a2, … ak может быть записан следующем образом:

k

b= p11a p21a p … k1ap= i1ai

i=1

k

b= p12a p22a p … k2ap= i2ai

i=1

----------------------------------------------

k

bj = p1ja p2ja p … kjap= ijai

i=1

----------------------------------------------

k

br = p1ra p2ra2  p … krap= irai

i

Рассмотрим теперь метод построения образующей матрицы

Из свойств группового следует, что

dW min

С другой стороны Wi = Wнi  d+ Wпi min

Wп dmin – Wн

Т.к. вес всех сторон ||Н||:W11=1, то имеем

dWп min – 1, dmin  d t+1min  t–1

dWп min  t Wп  t – 1

Необходимые и Отсюда: для кодов, обнаруживающихt– кратные ошибки:

достаточные требования Wп (строки)  t

для построения проверочной для кодов, исправляющих t – кратные ошибки :

матрицы Wп (строки)  2t

Рассмотрим частные случаи:

1.) Коды, обнаруживающие одиночную ошибку.

dmin= 2 ( N=15, t=1 )

Wп 1

Единая матрица для dmin2

100…0 1 k k

010…0 1 ba=ip1i a=Не что иное, как

001…0 1 i=1 i=1 проверка на четность.

000…1 1

И П

Во всех комбинациях построенного кода – четное.

Для dmin  3 проверочная матрица не может быть представлена в общей (единой) форме, т.к. дляdmin  r зависит отk. 3 


Построение кодовой комбинацииEв матричной форме имеет вид:

образующая матрица

E = IGn,k , гдеI– вектор длиныk, компонентами которой являются

информационные разряды.

кодовый вектор информационный

вектор

2.2 Представление кодов в виде кодовых деревьев

Кодовое дерево - связной граф, не содержащий циклов. Связной граф - граф, в котором для любой пары вершин существует путь, соединяющий эти вершины. Граф состоит из узлов (вершин) и ребер (ветвей), соединяющих узлы, расположенные на разных уровнях[4]. Для построения дерева равномерного двоичного кода выбирают вершину называемую корнем дерева (истоком) и из нее проводят ребра в следующие две вершины и т.д.

Пример кодового дерева для полного кода приведен на рис.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

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

2.3 Представление кодов в виде многочленов

Описание циклических кодов и их построение удобно проводить с помощью многочленов (или полиномов). Запись комбинации в виде полинома понадобилась для того, чтобы отобразить формализованным способом операцию циклического сдвига исходной кодовой комбинации. Так, n-элементную кодовую комбинацию можно описать полиномом (n − 1) степени, в виде[5]:

An−1(x) = an−1 xn−1 + an−2 xn−2 + … + a1 x + a0,

где ai = {0, 1}, причем ai = 0 соответствуют нулевым элементам комбинации, ai = 1 — ненулевым.

Запишем полиномы для конкретных 4-элементных комбинаций:

1101 ⇔ A1(x) = x3 + x2 + 1
1010 ⇔ A2(x) = x3 + x

Операции сложения и вычитания выполняются по модулю 2. Они являются эквивалентными и ассоциативными:

  • G1(x) + G2(x) ⇒ G3(x)
  • G1(x) − G2(x) ⇒ G3(x)
  • G2(x) + G1(x) ⇒ G3(x)

Примеры

  • G1(x) = x5 + x3 + x
  • G2(x) = x4 + x3 + 1
  • G3(x) = G1(x) ⊕ G2(x) = x5 + x4 + x + 1

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

  • G1(x) = x6 + x4 + x3
  • G2(x) = x3 + x2 + 1

x6 + x4 + x3 | x3 + x2 + 1

+------------

x6 + x5 + x3 | x3 + x2

------------

x5 + x4

x5 + x4 + x2

------------

x2

2.4 Геометрическое представление кодов

Числовая информация может быть представлена геометрически. Например, на различных приборах с циферблатом: часах, спидометре числовое значение времени (скорости) кодируется положением стрелки на круговой шкале (или на линейной). Геометрическое представление числовой информации - это также и различные диаграммы: круговые, столбчатые. Такое представление информации является очень удобным и наглядным.

Примером кодирования информации является условное обозначение силы подземных толчков при землетрясениях. Здесь рисунки со степенями разрушения здания занумерованы от 1 до 10 (вспомните учебник по географии). При указании на силу подземных толчков называют количество баллов по выбранной 10-бальной шкале. А на географической карте зоны землетрясений обозначаются концентрическими окружностями, где эпицентр бедствия является их центром[6]. Здесь отношение "сильнее" закодировано отношением "содержать".

Любая комбинация n - разрядного двоичного кода может быть представлена как вершина n - мерного единичного куба, т.е. куба с длиной ребра равной 1. Для двухэлементного кода (n = 2) кодовые комбинации располагаются в вершинах квадрата. Для трехэлементного кода

(n = 3) - в вершинах единичного куба (рис.2).

В общем случае n мерный куб имеет 2n вершин, что соответствует набору кодовых комбинаций 2n.

n = 2 n = 3

Рисунок 2 - Геометрическая модель двоичного кода

Геометрическая интерпретация кодового расстояния. Кодовое расстояние - минимальное число ребер, которое необходимо пройти, чтобы попасть из одной кодовой комбинации в другую. Кодовое расстояние характеризует помехоустойчивость кода[7].

Заключение

В данной работе были рассмотрены вопросы понятия кодирования данных, изучены типы кодов, рассмотрены методы кодирования данных.


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

Дело в том, что физические устройства (регистры, ячейки памяти) могут находиться в двух состояниях, которым соотносят 0 или 1. Используя ряд подобных физических устройств, можно хранить в памяти компьютера почти любое число в двоичной системе счисления. Сколько физических ячеек используемых для записи числа, столько и разрядное число можно записать. Если ячеек 8, то и число может состоять из 8 цифр.

Кодирование в компьютере целых чисел, дробных и отрицательных, а также символов (букв и др.) имеет свои особенности для каждого вида. Например, для хранения целых чисел выделяется меньше памяти (меньше ячеек), чем для хранения дробных независимо от их значения.

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

В общем смысле кодирование информации можно определить как перевод информации, представленной сообщением в первичном алфавите, в последовательность кодов.

Надо понимать, что любые данные - это так или иначе закодированная информация. Информация может быть представлена в разных формах: в виде чисел, текста, рисунка и др. Перевод из одной формы в другую - это кодирование.

Список использованной литературы

1. Артамонов В.С., Серебряков Е.С. «Персональный компьютер для начинающих». - М. -СПб., 2000 – 315с.

2. Дмитриев В.И. Прикладная теория информации. М.: Высшая школа. Электронный учебник

3. Информатика: Учебник для вузов. Под ред. Симоновича.- СПб., 2000- 640с.

4. Информатика: Учебник Под ред Н.В. Макаровой.- М., 2000 – 768с.

5. Кловский Д.Д. Теория передачи сигналов. -М.: Связь, 1984. – 288с.

6. Колесник В.Д., Полтырев Г.Ш. Курс теории информации. М.: Наука, 2006. – 345с.

7. Кудряшов Б.Д. Теория информации. Учебник для вузов Изд-во ПИТЕР, 2008. - 320с.

8. Семенюк В.В. Экономное кодирование дискретной информации. - СПб.: СПбГИТМО (ТУ), 2001 – 434с.

10.Рябко Б.Я., Фионов А.Н. Эффективный метод адаптивного арифметического кодирования для источников с большими алфавитами // Проблемы передачи информации. - 1999. - Т.35, Вып. - С.95 - 108.

  1. Артамонов В.С., Серебряков Е.С. «Персональный компьютер для начинающих». - М. -СПб., 2000 – С. 12.

  2. Информатика: Учебник для вузов. Под ред. Симоновича.- СПб., 2000- С. 24-25.

  3. Дмитриев В.И. Прикладная теория информации. М.: Высшая школа. Электронный учебник

  4. . Информатика: Учебник Под ред Н.В. Макаровой.- М., 2000 – С. 56-57.

  5. Кловский Д.Д. Теория передачи сигналов. -М.: Связь, 1984. – С. 67.

  6. Рябко Б.Я., Фионов А.Н. Эффективный метод адаптивного арифметического кодирования для источников с большими алфавитами // Проблемы передачи информации. - 1999. - Т.35, Вып. - С.95 - 108

  7. Семенюк В.В. Экономное кодирование дискретной информации. - СПб.: СПбГИТМО (ТУ), 2001 – С. 110.