cl-Ast-informatikaУЧЕБНОЕ ПОСОБИЕ

Хэмминга

Голея

Макдональда

Варшамова

С малой плотностью проверок на четность

Итеративный

Коды циклические

Хэмминга

Боуза-Чоудхури

Мажориторный

Милса-Абрамсона

Рида-Соломона

3.3ХАРАКТЕРИСТИКИ КОДОВ

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

кодов m=2. Значения импульсных признаков цифры 0 и 1.

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

Полное число кодовых комбинаций N — число всех возможных комбинаций длины n из m различных символов, равное mn (для двочных кодов N = 2n).

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

Число проверочных символов r — количество символов (разрядов) кодовой комбинации, необходимых для коррекции ошибок.

Под избыточностью кода R понимают относительную избыточность, равную отношению числа проверочных символов к длине кода:R = r/n

Скорость передачи кодовых комбинаций — отношение числа информационных символов к длине кода: R’ = k/n.

Вес кодовой комбинации (кода) w — количество единиц в кодовой комбинации.

Кодовое расстояние d между двумя кодовыми комбинациями — число одноименных разрядов с различными символами. Практически кодовое расстояние выражается как вес суммы кодовых комбинаций.

Пример 1. Определить кодовое расстояние между комбинациями 100101 и 001001. Просуммируем их по модулю два:

100101

+

001001

101100

Полученная в результате суммирования новая кодовая комбинация характеризуется весом w = 3. Следовательно, кодовое расстояние между исходными комбинациями d = 3.

Весовая характеристика кода W(w) — число кодовых комбинаций веса w.

Пример 2. Даны кодовые комбинации 00000, 11110, 11101 и 11010, весовая характеристика W(0) = 1, W(3) = 1, W(4) = 2, т. е. данный код состоит из одного кодового слова веса 0, двух слов веса 4 и одного слова веса 3.

119

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

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

3.4 МЕТОДЫ КОДИРОВАНИЯ ИНФОРМАЦИИ

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

Увеличение емкости ГМД в 10 раз по сравнению с первоначальным было достигнуто в результате улучшения механической части дисковода(40%)и внедрения методов кодирования данных, позволяющих эффективно использовать рабочую поверхность(60%).

Метод FM

Кодирование с применением FM-сигналов принято называть кодированием с единичной плотностью. В начале битовых элементов записываются биты синхронизации, а в промежутках между ними биты данных. Битовый элемент определяется как минимальный интервал времени между битами данных, получаемых при постоянной скорости вращения диска (для диска 3,5” длительность битового элемента 8 мкс). Бит данных записывается через 4 мкс после бита синхронизации. Недостаток: почти половина полезной емкости используется для записи служебной информации. Для жестких магнитных дисков этот метод не применяется.

Пример. диск 5,25”; запись информации с плотностью 50 tpi (дорожек на дюйм) на одной стороне, емкость диска 110 Кбайт. Удалось повысить плотность до 100 tpi с удвоением продольной плотности, емкость повысилась до 500 Кбайт (70-е годы).

Методы MFM и M2FM — модифицированная частотная модуляция и миллеровская модифицированная частотная модуляция. После внедрения двусторонней записи по этому методу емкость возросла до 1 Мбайта. Метод FM позволяет вдвое увеличить продольную плотность записи. Длительность битового элемента 4 мкс. Биты синхронизации записываются если в предыдущем и текущем битовых элементах не были записаны биты данных. На каждой дорожке можно записывать 6,25 Кбайт данных. Скорость обмена данными 5 Мбайт/с.

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

Метод RLL — метод записи с групповым кодированием. Впервые был использован в цифровой записи на магнитную ленту. Каждый байт данных делится на 2 полубайта, которые кодируются 5-разрядным кодом. При считывании каждые две 5- разрядные группы декодируются и полубайты объединяются. Скорость передачи данных до 380 Кбайт/с; длительность битового элемента 2,6 мкс. На каждой дорожке можно записывать 7,6 Кбайт данных. Скорость обмена данными 7,5 Мбайт/с.

Метод ARLL — модифицированный RLL. Наряду с уплотнением данных увеличена скорость обмена данными между накопителями и контролером. Скорость обмена данными 10 Мбайт/с.

Метод PRML использует алгоритм частного срабатывания по максимальной вероятности. Для жестких магнитных дисков скорость обмена данными в 10-20 раз больше, выше плотность записи.

120

3.5КОНТРОЛЬ ПЕРЕДАЧИ ИНФОРМАЦИИ. ПОМЕХОУСТОЙЧИВОЕ

КОДИРОВАНИЕ

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

Если длина кода n разрядов, то таким двоичным кодом можно представить максимум 2n различных слов. Если все разряды слова служат для представления информации, код называется простым.

Коды разделяются на равномерные и неравномерные. В равномерных кодах все слова содержат одинаковое число разрядов. В неравномерных кодах число разрядов в словах может быть различным. В вычислительных машинах применяются преимущественно равномерные коды.

Равномерные избыточные коды делятся на разделимые и неразделимые.

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

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

Способность кода обнаруживать или исправлять ошибки определяется так называемым минимальным кодовым расстоянием (минимальное расстояние между двумя любыми словами в этом коде).

Если имеется хотя бы одна пара слов, отличающихся друг от друга только в одном разряде, то минимальное расстояние данного кода равно 1.

Простой код имеет минимальное расстояние dmin = 1. Для избыточных кодов dmin > 1.

Если dmin ≥ 2, то любые два слова в данном коде отличаются не менее чем в двух разрядах, следовательно, любая одиночная ошибка приведет к появлению запрещенного слова и может быть обнаружена.

Если dmin = 3, то любая одиночная ошибка создает запрещенное слово, отличающееся от правильного в одном разряде, а от любого другого разрешенного слова

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

Для того, чтобы избыточный код позволял обнаруживать ошибки кратностью r, должно выполняться условие: dmin ≥ r + 1

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

3.5.1. Код с проверкой четности

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

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

Минимальное расстояние кода dmin = 2, поэтому код с проверкой четности обнаруживает все одиночные ошибки и все случаи нечетности числа ошибок (3,5 и т. д.). При одновременном возникновении четного числа ошибок код с проверкой четности не

121

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

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

3.5.2. Контроль по совпадению

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

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

3.5.3. Код Хэмминга

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

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

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

Пусть кодовое слово длиной n разрядов имеет m информационных и k = n - m контрольных разрядов. Корректирующее число длиной k разрядов описывает 2k состояний, соответствующих отсутствию ошибки и появлению ошибки в 1-м разряде. Таким образом, должно соблюдаться соотношение:

2k = n - 1 или 2k - k + 1 = m

Из этого следует, что пять контрольных разрядов позволяют передавать в коде Хэмминга до 26 информационных разрядов. Если в ОП одновременно записываются или считываются восемь информационных байт (64 разряда), то при использовании кода Хэмминга потребуется семь дополнительных контрольных разрядов.

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

Модифицированный код Хэмминга

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

Пусть Х — слово, записанное в ОП, а Х' — считанное из ОП слово, в котором обнаружены две ошибки. Тогда по сигналу схемы контроля инициируется следующая процедура:

•в неисправную ячейку ОП записывается обратный код считанного слова X'

изатем производится его считывание;

122

• над получаемым при этом кодом ( X' )' и кодом X' производится операция сложения по модулю 2.

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

Пример. Построение кода Хэмминга с кодовым расстоянием d=3.

Пусть число передаваемых сообщений равно 16, тогда число информационных элементов k=log216=4. Если выписать все 16 возможных комбинаций, то получим исходный (простой) код. Возьмем только 4 кодовых комбинации в виде единичной матрицы

1000

0100 (1)

0010

0001

Каждую кодовую комбинацию дополним справа проверочными элементами так, чтобы d=3. Нулевая комбинация относится к числу разрешенных комбинаций корректирующего кода, следовательно в проверочные элементы надо добавить не менее двух единиц.

1000|11 0100|11 (2) 0010|11 0001|11

Сложим первые две строки матрицы (2) по модулю 2. 100011

+

010011

110000

Так как отличие только в двух элементах, то d=3 не обеспечено. Добавим проверочные элементы следующим образом. (можно и в другом виде)

1000|111 0100|101 (3) 0010|011 0001|110

Получили порождающую матрицу кода G(7,4), содержащего 7 элементов, 4 из которых — информационные. Суммируя в различном сочетании строки матрицы (3), получим все (за исключением нулевой) комбинации корректирующего кода с кодовым расстоянием 3.

Пусть а1-а7 — элементы корректирующего кода,

а1-а4 — информационные разряды, а5-а7 — проверочные разряды.

Правило формирования проверочного элемента аj (верно для любой кодовой комбинации): Проверочные разряды могут быть получены суммированием по модулю 2 определенных информационных элементов кода. Смотрим столбец аj в проверочных разрядах. Если элемент aij=1, то в соответствующей строке i в суммировании участвует информационный элемент, равный 1.

Пример.

По матрице (3) сформируем элементы а5-а7.

а5=а1 а2 а4 а6=а1 а3 а4 (*) а7=а1 а2 а3

123

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

Пусть передана кодовая комбинация 100011101, а принята 110011101. Подставим в проверочные выражения (*)

а5`=1 1 0 = 0 ≠ a5 а6`=1 0 0 = 1 = a6 а7`=1 1 0 = 0 ≠ a7

Синдром (проверочный вектор) определяется комбинацией s1s2s3.

s1=a5 а5` = 1; s2=a6 а6` = 0; s3=a7 а7`=1

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

Таким образом, синдром 101 указывает на ошибку во втором разряде, для исправления которой элемент а2 меняется на противоположный. Код G(7,4) обнаруживает двукратные ошибки, а исправляет только однократные.

КЛЮЧЕВЫЕ ПОНЯТИЯ

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

Датаграмма — самостоятельный пакет, движущийся по сети независимо от других пакетов.

Избыточность кода — отношение числа проверочных символов к длине кода.

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

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

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

Код ASCII (American Standard Code for Information Interchange — Американский стандартный код для обмена информацией)

Кодирование — процесс преобразования сообщений в комбинации из дискретных сигналов.

Кодовое расстояние между двумя кодовыми комбинациями — число одноименных разрядов с различными символами.

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

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

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

124

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

Полное число кодовых комбинаций — число всех возможных комбинаций длины n из m различных символов, равное mn.

Разряд — место для цифры в числе. Разрядность — количество цифр в числе.

Скорость передачи кодовых комбинаций — отношение числа информационных символов к длине кода.

Такт — временной интервал между двумя соседними моментами дискретного времени. Линия связи — это среда, по которой передаются сигналы от передатчика к приемнику. Трафик — нагрузка, создаваемая потоком вызовов, требований, сообщений, поступающих на входы системы массового обслуживания.

Уплотнение каналов связи — статическое разделение канала, при котором определенные полосы частот (или периоды времени) выделяются в фиксированном порядке для использования в качестве отдельных каналов.

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

Число проверочных символов — количество символов (разрядов) кодовой комбинации, необходимых для коррекции ошибок.

ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ

1.Как изображаются числа СФТ и СПТ?

2.Для чего используются упакованный и распакованный форматы?

3.Какие существуют правила для выполнения арифметических действий в двоичной системе счисления?

4.Есть ли разница в порядке перевода целых и дробных числе из одной системы счисления в другую?

5.Как получить дополнительный код числа?

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

7.Как формируются последовательный и параллельный коды?

8.В чем сущность асинхронной передачи?

9.Какие существуют помехи в каналах связи?

10.В чем смысл коммутации в сетях?

11.Для чего используется датаграммный режим передачи пакетов?

12.Чем характеризуются коды?

13.Перечислите методы кодирования информации.

14.Какие коды используют для помехоустойчивого кодирования?

ТЕСТЫ ДЛЯ САМОКОНТРОЛЯ

3.Для разрядной сетки, в которой число разрядов целой и дробной части равно 5, записать число 34,627

4.Записать число 34,627в нормальной форме

5.Записать число35 в упакованном формате

6.Записать число 35 в распакованном формате

7.Сложение в 2 с/с А=11011 В=101010

8.Вычитание в 2 с/с А=101010 В=11011

125

16.Помеха, представляющая собой напряжение, меняющееся в времени случайным образом, называется

17.Помеха, приближенно описываемая синусоидальным колебанием, называется

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

20.Минимальный интервал времени между битами данных при постоянной скорости вращения диска называется

21.Если в коде все слова содержат одинаковое количество разрядов, то код называется

22.Если в коде все разряды слова служат для представления информации, то код называется

23.Способность кода обнаруживать и исправлять ошибки определяется

24.Если при передаче информации ее правильность проверяется поразрядным сравнением, то это контроль

25.Полное пропадание информации при передаче контролируется кодом с проверкой

За каждый правильный ответ поставьте себе 1 балл. Просуммируйте набранные баллы и разделите полученную сумму на 5. Округлите результат. Это ваша оценка за тест.

РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА

1.Острейковский. Информатика:Учеб. для техн. направлений и спец. вузов.-М.: Высш.

шк., 1999.- 512 с.:рис.

2.Информатика: Учебник/Под ред. Н. В. Макаровой.-М.: Финансы и статистика, 2003.- 768 с., ил.

3.Кодирование информации: Двоичные коды. Справочник/Под ред. Березюка Н. Т.- Харьков: Вища шк, 1978.- 251 с.,ил.

4.Ситников Ю. К. Основы цифровой ВТ: Учеб. пособие.-[Казань]: Изд-во казан. ун-та, 1992.- 167 с.

5.Андреева Е., Фалина И. Системы счисления и компьютерная арифметика.-М.: Лаборатория Базовых Знаний, 1999.- 256 с.

6.Сергиенко А. Б. Цифровая обработка сигналов.-СПб.: Питер, 2002.- 608 с.

7.Хелд Г. Технологии передачи данных. 7-е изд.-СПб.: Питер, 2003.- 720 с.

8.Периодические издания: журналы "Компьютер-пресс", "Мир ПК", "Монитор", "Компьютерра".

126

Цель: ознакомление с историей развития новых информационных технологий и компьютерными офисными технологиями на примере ППП Microsoft Office.

Задачи:

¾Ознакомиться с общими понятиями и принципами информационных технологий.

¾Ознакомиться с интерфейсом и функциональными возможностями компонентов

ППП Microsoft Office.

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

После изучения модуля вы должны Знать:

¾Виды новых информационных технологий.

¾Технологию создания интегрированного документа на основе технологии OLE.

¾Типы и форматы данных, правила адресации в электронной таблице.

¾Типы и форматы данных, типы запросов в системе управления базами данных.

Результат:

¾Навыки профессиональной работы с приложениями MS Office.

¾Получение общего представления о базах данных и системах их управления.

¾Формирование начальной профессиональной базы для успешного овладения такими дисциплинами как «Объектно-ориентированное программирование», «Базы данных».

¾Пополнение профессионального словарного запаса.

Kритерии:

¾Сложность изучаемого материала (1 — простой, 2 — средний, 3 — 1 сложный)

¾Минимально необходимое время изучения материала (в аудиторных 1,5 часах) — 30% знаний

Лабораторное сопровождение:

¾Лабораторная работа №7 Работа в среде текстового процессора

¾Лабораторная работа №8 Работа в среде табличного процессора

¾Лабораторная работа №9 Работа в среде СУБД

¾Лабораторная работа №10 Работа в среде электронной презентации

127

1 ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ

1.1 ОБЩИЕ ПОНЯТИЯ

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

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

Цель информационной технологии — производство информации для ее анализа и принятия на его основе решения по выполнению какого-либо действия.

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

Новая информационная технология — информационная технология с

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

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

Основные принципы новой информационной технологии:

•интерактивный (диалоговый) режим работы с компьютером;

•интегрированность (взаимосвязь) с другими программными продуктами;

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

программное и математическое обеспечение этого процесса. С их помощью производится переработка первичной информации в информацию нового качества.

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

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

1.2 ИСТОРИЯ РАЗВИТИЯ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

Этапы обработки информации

1-й этап (60-70-е гг.) — обработка данных в вычислительных центрах в режиме коллективного пользования. Основное направление — автоматизация рутинных действий человека.

2-й этап (с 80-х гг.) — создание информационных технологий, направленных на решение стратегических задач.

Этапы информатизации общества

1-й этап (до конца 60-х гг.) — проблема обработки больших объемов данных в условиях ограниченных возможностей аппаратных средств.

2-й этап (до конца 70-х гг.) — распространение ЭВМ серии IВМ/360. Проблема отставания программного обеспечения от уровня развития аппаратных средств.

128