Методические указания к выполнению курсовых работ по курсу «Схемотехника эвм»




НазваниеМетодические указания к выполнению курсовых работ по курсу «Схемотехника эвм»
страница6/7
Дата конвертации26.10.2012
Размер1.1 Mb.
ТипМетодические указания
1   2   3   4   5   6   7
ПОМЕХОУСТОЙЧИВЫЕ ПОЛИНОМИАЛЬНЫЕ КОДЫ

К помехоустойчивым полиномиальным кодам (ППК) относятся широко известные циклические коды, такие как циклический код Хэмминга, код Файра, код Абрамсона, БЧХ-код и д.р. Основная особенность этих кодов состоит в том, что они строятся на основе образующих полиномов g(x) = gkxk + gk-1xk-1 + ... + g1x + g01, где коэффициенты gi для двоичных кодов принимают значения нуля или единицы.

Циклические коды широко применяются при построении устройств вычислительной техники и вычислительных сетей.

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

CRC (Cyclic redundancy check) - код циклического контроля. Термин используется только для помехоустойчивых циклических кодов обнаруживающих ошибки. Буквами CRC также указываются разряды (байты), отводимые в формате под контрольные (избыточные) символы, формируемые при передаче (записи). При приеме (чтение) с помощью этих символов определяется отсутствие или наличие ошибки.

EDC (Error Diagnostic Codes) - помехоустойчивые коды, обнаруживающие ошибки. Термин используются для всех помехоустойчивых кодов, обнаруживающих ошибки. Буквами EDC также указываются разряды (байты), отводимые в формате под контрольные символы, формируемые при передаче (записи) информации. При приеме (чтении) с помощью этих символов определяется наличие или отсутствие ошибки.

ECC (Error Correction Codes) - помехоустойчивые коды, исправляющие ошибки. Буквами ECC указываются также разряды (байты), отводимые в формате для контрольных символов, формируемых при передаче (записи). При приеме (чтении) с помощью этих символов определяется наличие ошибки и проводится исправление.

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

Приведем некоторые примеры применения циклических кодов.

В накопителях на гибких магнитных дисках все операции записи данных сопровождаются формированием и записью в конце поля после 512 информационных байт (сектор) 2 байт CRC.

В накопителях на жестких магнитных дисках (НЖМД) используются циклические коды, исправляющие ошибки (ECC). Фирмы-производители НЖДМ включают схемы формирования ECC и исправления ошибок в контроллеры жестких дисков. Поскольку в настоящее время используются НЖДМ со встроенными контроллерами, то пользователю и не сообщается о конкретном используемом коде. Например, в ряде контроллеров для сектора длиной 512 байт формируется ECC длиной 7 байт.

Описание помехоустойчивого полиномиального кода.

Полиномиальный код является блоковым, т.е. состоит из n – разрядных кодовых слов. Кодовые слова составляются из алфавита кода. Количество элементов алфавита Q. Если Q = 2, то код двоичный. Контрольные разряды в блоковом коде зависят только от информационных разрядов данного кодового слова.

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

w вес комбинации, т.е. количество единиц в комбинации.

dmin – минимальное кодовое расстояние, которое равно минимальному кодовому расстоянию всех возможных комбинаций кода.

dmin определяет способность помехоустойчивого кода обнаруживать и исправлять ошибки:

dminr + 1; dmin ≥ 2s + 1; dmins + r + 1 (если s < r),

(1)

где r – количество ошибок в кодовом слове, которые код сможет обнаружить; s – количество ошибок в кодовом слове, которые код сможет исправить.

Кодирование помехоустойчивым полиномиальным кодом

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

Кодовое слово состоит из двух частей (рис. 12): информационный блок в неизменном виде (длина m) + контрольный блок (длина k).



Рис. 12. Структура кодового слова

Таким образом, длина кодового слова n = m + k.

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

Например, необходимо передать байт информации, который в двоичном виде равен 11011101, тогда разрядность информационного блока равна 8 (байт). Необходимо исправить 2 независимые ошибки, тогда образующий полином в виде коэффициентов будет равен 100111001, а в полиномиальном виде – x8 + x5+x4+x3+1. Длина контрольного блока k будет равна 8, тогда длина кодового слова n равна 16 (8+8).

В процессе кодирования нам необходимо получить остаток от деления Rg(x)a(x)∙xk, где a(x) – информационный блок в полиномиальном виде.

В случае примера

a(x) = a7x7+ a6x6+ a5x5+ a4x4+ a3x3+ a2x2+ a1x+ a0∙1 = 1∙x7+ 1∙x6+ 0∙x5+ 1∙x4+ 1∙x3+ 1∙x2+ 0∙x+ 1∙1 = x7+ x6+ x4+ x3+ x2+ 1.

Помножив a(x) на xk (в нашем примере x8), получим

a(x)x8= x15+ x14+ x12+ x11+ x10+ x9 или 1101110100000000

в виде двоичных коэффициентов.

Остатком от деления двоичных чисел по модулю два 1101110100000000 на 100111001 будет являться двоичное число 10011110 (описание деления по модулю два приведено ниже).

Полученный остаток добавляем к двоичному числу 1101110100000000 и получаем кодовое слово, равное 1101110110011110 (в виде двоичного числа) или x15+ x14+ x12+ x11+ x10+ x8+ x7 + x4+ x3+ x2+ x (в полиномиальном виде).

Декодирование помехоустойчивым полиномиальным кодом

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

После того, как ошибка была исправлена (или её не было), извлекаются информационные разряды из кодового слова. Информационными разрядами являются старшие m разрядов кодового слова a.

Проверка на наличие ошибки производится делением кодового полинома a(x) на образующий полином g(x) (Rg(x)(a(x))). Если остаток равен нулю, то ошибка отсутствует или искажено больше разрядов, чем код может обнаружить. Иначе (когда остаток ненулевой) ошибка присутствует, но ещё не известно сможет код исправить эту ошибку или нет, так как остаток от деления свидетельствует об ошибке, но не указывает на неё (подробнее о методах исправления ошибки описано ниже).

Деление полиномов по модулю два

“Классический” алгоритм

Повышение скорости кодирования/декодирования (особенно декодирования) данных при использовании циклических кодов зависит от скорости деления полиномов вида:

,

(2)

где ai, bj {0, 1}; i = ; j = ; n m; n – количество разрядов делимого, m –делителя.

Деление полиномов вида (2) эквивалентно делению двоичного числа {anan-1an-2a0} на двоичное число {bmbm-1bm-2b0} в арифметике по модулю два. Например, операция деления полинома (x7 + x5 + x3 + x + 1) на полином (x4 + x + 1) сводится к делению числа 10101011 на число 10011.

Отметим, что аппаратурная или программная реализация процесса деления полиномов является многошаговой. В результате выполнения i – го шага получается очередное значение Ri промежуточного (i =) или окончательного (i = k) остатка.

Количество шагов k равно числу ненулевых разрядов частного.

Из-за необходимости выполнения большого числа шагов операция деления является одной из наиболее медленных операций ЭВМ.

Пример обычного деления:



МАТРИЧНЫЙ АЛГОРИТМ

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

Пусть n – разрядность делимого, а k+1 – разрядность делителя, тогда:

– делимое, а – делитель. (2)

Обозначим ; , и .

Определим матрицу :

, где (остаток от деления на делитель ).

Матрицу Y определим следующим образом:

, где (частное от деления на делитель ).


Начало: даны полиномы вида (2), где А – делимое, а В – делитель.

Шаг 1: вычислить матрицу Z для полинома :

,

где (остаток от деления на делитель ).

Шаг 2: вычислить матрицу Y для делимых разрядностью n:

,

где частное от деления на делитель .

Шаг 3: вычислить остаток .

Шаг 4: вычислить частное .

Шаг 5: конец.

Для быстрого формирования матриц и , существуют простые рекуррентные формулы:

, где - старший разряд ; i = ;

, где i = ;

, – начальные значения для рекуррентных формул.

Пусть n = 6, а m = 4 (B = 101). Для заполнения матрицы и обычным способом необходимо разделить x5, x4, x3 и x2 на , а используя предложенные формулы необходимо вычислить 8 простых выражений:

z3 = 01; y3 = 1;

z2 = 010  0  101 = 10; y2 = 10;

z1 = 100  1  101 = 01; y1 = 101;

z0 = 010  0  101 = 10; y0 = 1010.

Обычным способом:



z0 = 10; y0 = 1010; z1 = 01; y1 = 101; z2 = 10; y2 = 10; z3 = 01; y3 = 1.

ТАБЛИЧНЫЙ СПОСОБ ДЕКОДИРОВАНИЯ ППК

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

Сам процесс декодирования ППК табличным методом состоит из следующих этапов:

  • вычисление синдрома ошибки;

  • формирование исправляющей комбинации;

  • исправление информационного блока или формирование сигнала о неисправимой ошибке.

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

КОДЕК ППК С ИСПОЛЬЗОВАНИЕМ МАТРИЧНОГО ДЕЛЕНИЯ
1   2   3   4   5   6   7

Похожие:

Методические указания к выполнению курсовых работ по курсу «Схемотехника эвм» iconМетодические указания по выполнению курсовых работ
Методические указания по выполнению курсовых работ рассмотрены и утверждены на заседании кафедры «Экономика на предприятиях туризма...

Методические указания к выполнению курсовых работ по курсу «Схемотехника эвм» iconМетодические указания по выполнению курсовых работ
Методические указания по выполнению курсовых работ рассмотрены и утверждены на заседании кафедры «Маркетинг на предприятиях туризма...

Методические указания к выполнению курсовых работ по курсу «Схемотехника эвм» iconМетодические указания по выполнению курсовых работ
Методические указания по выполнению курсовых работ рассмотрены и утверждены на заседании кафедры «Экономика на предприятиях туризма...

Методические указания к выполнению курсовых работ по курсу «Схемотехника эвм» iconМетодические указания по выполнению курсовых работ
Методические указания по выполнению курсовых работ рассмотрены и утверждены на заседании кафедры «Экономика на предприятиях туризма...

Методические указания к выполнению курсовых работ по курсу «Схемотехника эвм» iconМетодические указания по выполнению курсовых работ
Абдуллина И. А., Глобов К. С. Методические указания по выполнению курсовых работ. – Казань: Познание 2009–26 с

Методические указания к выполнению курсовых работ по курсу «Схемотехника эвм» iconМетодические указания по выполнению курсовых работ
Методические указания по выполнению курсовых работ рассмотрены и утверждены на заседании кафедры психологии

Методические указания к выполнению курсовых работ по курсу «Схемотехника эвм» iconМетодические указания по выполнению курсовых работ
Методические указания по выполнению курсовых работ рассмотрены и утверждены на заседании кафедры «Менеджмент»

Методические указания к выполнению курсовых работ по курсу «Схемотехника эвм» iconМетодические указания по выполнению курсовых работ
Методические указания по выполнению курсовых работ рассмотрены и утверждены на заседании кафедры «Менеджмент»

Методические указания к выполнению курсовых работ по курсу «Схемотехника эвм» iconМетодические указания по выполнению курсовых работ 1,75
Организация производства и менеджмент в машиностроении: методические указания по выполнению курсовых работ

Методические указания к выполнению курсовых работ по курсу «Схемотехника эвм» iconМетодические указания по выполнению курсовых работ Красноярск 2004 ^ I. Цель и задачи курсовой работы
Криминалистика. Методика расследования отдельных видов преступлений: Методические указания по выполнению курсовых работ / Сост. И....


Разместите кнопку на своём сайте:
lib.convdocs.org


База данных защищена авторским правом ©lib.convdocs.org 2012
обратиться к администрации
lib.convdocs.org
Главная страница