Лекция 6. Анализ и синтез информационных систем. 10 страница

В двоичном коде синдром записывается в двоичной системе, т.е. его разряды принимают значения 0 или 1.

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

Корректирующие коды делятся на блочные и непрерывные.

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

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

Разновидностями блочных и непрерывных кодов являются разделимые и неразделимые коды. В разделимых кодах всегда можно указать информационные и проверочные символы, в неразделимых - такое разделение символов провести невозможно.

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

Для систематических кодов применяется обозначение (п, к) - код, где п - общее число символов в кодовой комбинации, к - число информационных символов.

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

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

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

Циклические коды (или систематические): циклическая перестановка символов разрешенной комбинации дает снова разрешенную кодовую комбинацию.

При циклической перестановке символы кодовой комбинации перемещаются слева направо на одну позицию, причем крайний правый символ переносится на место крайнего левого. Например: при Ai = 101100 циклической перестановкой получаем А2=010110. В теории циклических кодов все преобразования кодовых комбинаций производятся в виде математических операций над полиномами. Для этого кодовые комбинации циклического кода представляют в форме полиномов. Если кодовая комбинация A=a_na_n_i...aiao при ai={l,0} записывается в виде:

A(x)=a„xⁿ+a„. i х¹¹"¹ +...a ix+ayx"

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

Лекция 15, Циклические коды, Техническая реализация циклических кодов.

Широкое распространение на практике получил класс линейных кодов, которые называются циклическими. Данное название происходит от основного свойства этих кодов, а именно, если некоторая кодовая комбинация принадлежит циклическому коду, то комбинация, полученная циклической перестановкой исходной комбинации (циклическим сдвигом), также принадлежит данному коду:

(ai, а2,..., а_п) —> (а„, ai, а2,..., a„-i)

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

Эти свойства используются при построении кодов, кодирующих и декодирующих устройств, а также при обнаружении и исправлении ошибок.

Циклические коды — это целое семейство помехоустойчивых кодов, включающее в себя в качестве одной из разновидностей коды Хэмминга, но в целом обеспечивающее большую гибкость с точки зрения возможности реализации кодов с необходимой способностью обнаружения и исправления ошибок, возникающих при передаче кодовых комбинаций по каналу связи. Циклический код относится к систематическим блочным (n, к)- кодам, в которых к первых разрядов представляют собой комбинацию первичного кода, а последующие (п - к) разрядов являются проверочными.

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

При декодировании принятой n-разрядной кодовой комбинации опять производится деление на порождающий полином.

Синдромом ошибки в этих кодах является наличие остатка от деления принятой кодовой комбинации на производящий полином. Если синдром равен нулю, то считается, что ошибок нет. В противном случае, с помощью полученного синдрома можно определить номер разряда принятой кодовой комбинации, в котором произошла ошибка, и исправить ее.

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

Пусть общее число бит в блоке равно п, из них полезную информацию несут в себе m бит, тогда в случае ошибки, имеется возможность исправить s бит. Зависимость s от п и m для кодов можно найти [6] в таблице:

Увеличивая разность п - щ можно не только нарастить число исправляемых бит s, но открыть возможность обнаружить множественные ошибки. Процент обнаруживаемых множественных ошибок, можно найти [6] в таблице:

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

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

Ai-i(x) = an-i х¹¹"¹ + а„-2 х"~² +... + а! х + а₍₎,

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

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

1101 I А(х) = х³+х²+1

1010 I Аз(х) = х³ + х

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

Gi(x) + G₂(x) = G₃(x) G₁(x)-G₂(x) = G₃(x) G₂(x) + Gi(x) = G₃(x)

Примеры

Gi(x) = x⁵ + x³ + x G₂(x) = x⁴ + x³ + 1

G₃{x) = Gi(x) I G₂(x) = x⁵ + x⁴ + x + 1 Операция деления является обычным делением многочленов, только вместо вычитания используется сложение по модулю 2: Gi(x) = х⁶ + х⁴ + х³ G₂{x) = х³ + х² + 1

х⁶ + х⁴ + х³ I х³ + х² + 1 +

х⁶ + х⁵ + х³ I х³ + х²

5,4 X + X

x⁵ + x⁴ + x²

x²

15.1 Циклический сдвиг кодовой комбинации

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

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

Допустим, задана исходная кодовая комбинация и соответствующий ей полином:

а(х) = а_пх" ¹ + a„-ix^{n 2} +... + а₂х + ai

Умножим а(х) на х:

а(х) • х = a_nx" + a„-ix^n_1 +... + агх² + aix

Так как максимальная степень х в кодовой комбинации длиной п не превышает (п — 1), то из правой части полученного выражения для получения исходного полинома необходимо вычесть а_п(х" - 1). Вычитание а„(х^п - 1) называется взятием остатка по модулю (х^п - 1).

Сдвиг исходной комбинации на i тактов можно представить следующим образом: а(х) • х - а„(х^п - 1), то есть умножением а(х) на х¹ и взятием остатка по модулю (х^п - 1). Взятие остатка необходимо при получении многочлена степени, большей или равной п.

15.2 Порождающий полином

Идея построения циклических кодов базируется на использовании неприводимых многочленов. Неприводимым называется многочлен, который не может быть представлен в виде произведения многочленов низших степеней, т. е. такой многочлен делится только на самого себя или на единицу и не делится ни на какой друтой многочлен. На такой многочлен делиться без остатка двучлен х¹¹ + 1. Неприводимые многочлены в теории циклических кодов играют роль образующих полиномов.

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

р(х) • х — С₂ (х^п-1) р(х) • х² - С₃ (х^п - 1)

р(х) • х"^1-1 - С_т (х" - 1)

где р(х) — исходная кодовая комбинация, на базе которой получены все остальные {m- 1) базовые комбинации, С[ = 0 или С[ = 1 («О», если результирующая степень полинома р{х) • х¹ не превосходит (п - 1), «1», если превосходит).

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

Порождающий полином должен удовлетворять следующим требованиям:

1. р{х) должен быть ненулевым;

2. вес р{х) не должен быть меньше минимального кодового расстояния: v{p{x)) > d_min;

3. р{х) должен иметь максимальную степень к (к — число избыточных элементов в коде);

4. р{х) должен быть делителем полинома (х^п - 1).

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

Для определения степени порождающего полинома можно воспользоваться выражением г > log₂{n+l), где п — размер передаваемого пакета за раз, т. е. длинна строящегося циклического кода.

Примеры порождающих полиномов, можно найти [5] в таблице:

Алгорит м получения разрешенной кодовой комбинации циклического кода из комбинации прост ого кода

Пусть задан полином Р(х) = a_r-i ^ + a_r-₂ x^{r l} +... + 1, определяющий корректирующую способность кода и число проверочных разрядов г, а также исходная комбинация простого к- элементного кода в виде многочлена Aj^i(x).

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

1. Умножаем многочлен исходной кодовой комбинации на х^г:

Aic-i(x) • х^г

2. Определяем проверочные разряды, дополняющие исходную информационную» комбинацию до разрешенной, как остаток от деления полученного в предыдущем пункте произведения на порождающий полином:

Ам(х) ' х^г/Р_г(х) I Щх)

3. Окончательно разрешенная кодовая комбинация циклического кода определится так: Ai-i(x) = Aj^i(x) • x^r + R(x) Для обнаружения ошибок в принятой кодовой комбинации достаточно поделить ее на производящий полином. Если принятая комбинация — разрешенная, то остаток от деления будет нулевым. Ненулевой остаток свидетельствует о том, что принятая комбинация содержит ошибки. По виду остатка (синдрома) можно в некоторых случаях также сделать вывод о характере ошибки, ее местоположении и исправить ошибку.

Пример. Пусть требуется закодировать комбинацию вида 1101, что соответствует А(х) = х³ + х^[i] + 1.

Определяем число контрольных символов г = 3. Из таблицы возьмем многочлен Р(х) = х³+х + 1, т. е. 1011.

Умножим А(х) на х:

А(х) • х^г = (х³ + х² + 1) • х³ = х⁶ + х^[ii] + х³ I 11010000

Разделим полученное произведение на образующий полином g(x):

А(х Где n — общее чиело элементов, m — число информационных элементов, к — число избыточных элементов {n = m + к).

Процедура построения кода БЧХ по заданным М и d_mi„:

1. по d_mi„ найти значение, при котором обеспечивается необходимое число информационных элементов m при минимальной избыточности k,_ni„;

2. найти в таблице соответствующий порождающий полином;

3. если d_mi„ четное, умножить найденный полином на (х + 1);

4. если т_тай_л» т,_адать то можно перейти к укороченному циклическому коду, вычеркивая в порождающей матрице исходного кода с параметрами ш_тай_л, k,ni„ (ш_тайл ~~ Щадап) столбцов слева и столько же строк сверху

Литература

1. Вернер М Основы кодирования. — М.: Техносфера, 2004.

2. ПитерсонВ., Уэлдон Ф. Коды, исправляющие ошибки. — М.: Мир,

1976.

1. J.-R. Abrial. The B-Book. - Cambridge University Press, 1996.

2. Калиниченко Jl.А СИНТЕЗ: язык определения, проектирования и программирования интероперабельных сред неоднородных информационных ресурсов. - Москва: ПИИ

РАН, 1993.

3. Л.А Калиниченко, С.А Ст упников, Н.А Земцов. Синтез канонических моделей для интеграции неоднородных источников информации. Москва, ИПИ РАН, 2005.

Тестовые задания для самоконтроля

1) Как записывается десятичное число "5" в двоичной системе счисления?

A) 101 Б) 110

B) 111 Г) 100 Д) 1111

2) Какое количество информации содержит один разряд двоичного числа?

A) 1байт Б) 3 бита

B) 4 бита Г) 1 бит Д) 2 бит

3) Как записывается десятичное число 4 в двоичной системе исчисления?

101 Б) 110

111 Г) 100 Д) 1111

4) Производительность работы компьютера (быстрота выполнения операций) зависит от...

A) размера экрана дисплея Б) частоты процессора

B) напряжения питания

Г) быстроты, нажатия на клавиши Д)человека

5) Какое устройство может оказывать вредное воздействие на здоровье человека?

A) принтер Б) монитор

B) системный блок Г) модем

Д) мышь

6) Дан список систем счисления: двоичная, десятичная, восьмеричная, шестнадцатеричная. Запись числа набором символов 100

A) отсутствует в десятичной

Б) существует во всех перечисленных

B) отсутствует в десятичной Г) отсутствует в восьмеричной Д) существует в двоичной

7) Объясните что такое, канал доступа к информации.

A) Физическая среда или технические средства, обеспечивающие возможность доступа человека к информации

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

B) Информация прикладных функциональных задач АСОД

Г) Уровень ответственности пользователя, работающего с этой информацией Д) Неизменность данных

8) Сколько байт в слове ТЕХНОЛОГИЯ

A) 192 Б) 80

B) 210 Г) 8

9) Сколько бит информации необходимо для кодирования одной буквы

A) 1 Б) 0

B) 8 Г) 16 Д) 32

Б) 135 В) 144 Г) 124 Д) 142

11) Чему равен 1 Гбайт...

A) 2¹⁰ Мбайт Б) 10³ Мбайт

B) 1000 Мбит

Г) 1000 ООО Кбайт Д) 100 Мбит

12) Преобразование непрерывных изображений и звука в набор диекретных значений в форме кодов называется

A) квантованием Б) дискретизацией

B) графикой

Г) специализацией Д) кодированием

13) Перечислите основные свойства информации

A) все ответы верны

Б) информация приносит знания об окружающем мире, которых в рассматриваемой точке не было до получения информации

B) информация не материальна, но она проявляется в форме материальных - дискретных знаков и сигналов или в форме функций времени

Г) информация может быть заключена как в знаках как таковых, так и в их взаимном расположении

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

14) Распознавание состоит в отождествлении с объектами и их отношениями в реальном

мире

A) знаков и сигналов Б)знаков

B) сигналов Г) объектов Д) цифрой

15) Из знаков или сигналов строятся последовательности, которые называются

A) сообщениями Б) сигналами

B) знаками

Г) алфавитами Д) сигналами и знаками

16) Процесс обратный кодированию называется....

A) кодированием Б) передачей

B) хранением

Г) декодированием Д) переносом

Б) сигналами В) знаками Г) сообщениями Д) сигналами и знаками

17) Какая мера количества информации называется вероятностной?

A) Энтропия +

Б) количественная

B) качественная Г) обобщенная

Д) логарифмическая

18) Назовите единицы измерения энтропии.

A) биты, наты, + Б) байты, наты

B) вольты, наты Г) кВт/ч, байты Д) амперы, наты

18) Чем определяется информация?

A) энтропией системы. +

Б) количеством информации

B) смыслом информации Г) ценностью информации Д) качеством информации

19) В каком случае энтропия системы равна нулю?

A) когда одно из состояний системы имеет вероятность, равную 1 + Б) когда одно из состояний системы имеет вероятность, равную» О

B) когда одно из состояний системы имеет вероятность, равную 0,5 Г) когда одно из состояний системы имеет вероятность, равную» 1,5 Д) когда одно из состояний системы имеет вероятность, равную» 2

Лабораторная работа 6. Информация и сообщение.

Цель работы: Экспериментальное определение информации из сообщений.

Теоретические сведения

«Информация есть всеобщее свойство материи и мера организации систем». Под информацией необходимо понимать не сами предметы и процессы, а их отражение или отображение в виде чисел, формул, описаний, чертежей, символов, образов. Сама по себе информация может быть отнесена к области абстрактных категорий, подобных, например, математическим формулам, однако работа с ней всегда связана с использованием каких- нибудь материалов и затратами энергии. Информация хранится в наскальных рисунках древних людей в камне, в текстах книг на бумаге, в картинах на холсте, в музыкальных магнитофонных записях на магнитной ленте, в данных оперативной памяти компьютера, в наследственном коде ДНК в каждой живой клетке, в памяти человека в его мозгу и т.д. Для ее записи, хранения, обработки, распространения нужны материалы (камень, бумага, холст, магнитная лента, электронные носители данных и пр.), а также энергия, например, чтобы приводить в действие печатающие машины, создавать искусственный климат для хранения шедевров изобразительного искусства, питать электричеством электронные схемы калькулятора, поддерживать работу передатчиков на радио и телевизионных станциях. Успехи в современном развитии информационных технологий в первую» очередь связаны с созданием новых материалов, лежащих в основе электронных компонентов вычислительных машин и линий связи. Информацию, представленную в формализованном виде, позволяющем осуществить ее обработку с помощью технических средств, называют данными.

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

По способу кодирования

По способу кодирования сигала информацию можно разделить на аналоговую и цифровую. Аналоговый сигнал информацию о величине исходного параметра, о котором сообщается в информации, представляет в виде величины другого параметра, являющегося физической основой сигнала, его физическим носителем. Например, величины углов наклона стрелок часов - это основа для аналогового отображения времени. Высота ртутного столбика в термометре - это тот параметр, который дает аналоговую информацию о температуре. Для отображения информации в аналоговом сигнале использувЯИ* все промежуточные знамения параметра от минимального до максимального, т.е. теоретически бесконечно большое их число. Цифровой сигнал использует в качестве физической основы для записи и передачи информации только минимальное количество таких значений, чаще всего только два. Например, в основе записи информации в ЭВМ применяются два состояния физического носителя сигнала -электрического напряжения. Одно состояние - есть электрическое напряжение, условно обозначаемое единицей (1), друтое - нет электрического напряжения, условно обозначаемое нулем (0). Поэтому для передачи информации о величине исходного параметра необходимо использовать представление данных в виде комбинации нулей и единиц, т.е. цифровое представление. Интересно, что одно время были разработаны и использовались вычислительные машины, в основе которых стояла троичная арифметика, так как в качестве, основных состояний электрического напряжения естественно взять три следующие: }) напряжение отрицательно, 2) напряжение равно нулю, 3)напряжение положительна. До сих пор выходят научные работы, посвященные таким машинам и

описывающие преимущества троичной арифметики. Сейчас в конкурентной борьбе победили производители двоичных машин. Будет ли так всегда? Приведем некоторые примеры бытовых цифровых устройств. Электронные часы с цифровой индикацией дают цифровую информацию о времени. Калькулятор производит вычисления с цифровыми данными. Механический замок с цифровым кодом тоже можно назвать примитивным цифровым устройством.

По сфере возникновения

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

По способу передачи и восприятия

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

По общественному назначению

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

Свойст ва информации

Информация имеет следующие свойства:

• • атрибутивные;

• • прагматические;

• * динамические.

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

Динамические свойства характеризуют изменение информации во времени.

Атрибутивные свойства информации

Неот рывност ь информации от физического носит еля и языковая природа

информации

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

Дискрет ноет ь

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

Неп ре рывност ь

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

Прагматические свойства информации

Смысл и новизна

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

Не нашли, что искали? Воспользуйтесь поиском: