Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Топ:
Теоретическая значимость работы: Описание теоретической значимости (ценности) результатов исследования должно присутствовать во введении...
Процедура выполнения команд. Рабочий цикл процессора: Функционирование процессора в основном состоит из повторяющихся рабочих циклов, каждый из которых соответствует...
Основы обеспечения единства измерений: Обеспечение единства измерений - деятельность метрологических служб, направленная на достижение...
Интересное:
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Дисциплины:
2017-11-16 | 298 |
5.00
из
|
Заказать работу |
|
|
Циклический код – это разновидность линейных блочных кодов (обладают теми же свойства). Дополнительное свойство: комбинация, полученная после циклической перестановки символов в последовательности, взятой из кодовой таблицы, принадлежит той же таблице. Коды разрабатывались для того чтобы для кодирования и декодирования можно было использовать простые устройства.
для описания n -разрядных комбинаций s, состоящих из M -ичных символов, удобно использовать полиномы
(3.36) |
где sj =0; 1;…; M -1.
Способы кодирования и декодирования конкретным циклическим кодом полностью определяются его производящим полиномом степени r
, | (3.40) |
где , причём всегда . Формально этот полином тоже содержит n членов, просто у него при .
Фундаментальное свойство циклического кода состоит в том, что полином s(x), соответствующий любой разрешённой (передаваемой) комбинации s, делится без остатка на производящий полином
. | (3.41) |
Отсюда следует метод декодирования принимаемой комбинации v (x): нужно вычислить остаток res(x) от деления этого полинома на g (x). Степень полинома res(x) не превышает r -1, то есть этот остаток содержит r бит. Если оказалось, что , то это несомненно указывает на наличие ошибок в принятой комбинации (обнаружение ошибок).
Напомним, что переданная s и принятая v комбинации связаны соотношение (3.2), откуда следует
v (x)= s (x)+ e (x), | (3.42) |
где e (x) – полином ошибок. Тогда с учётом (3.41) имеем соотношение, аналогичное формуле (3.17),
res(x)= v (x)mod g (x)= s (x)mod g (x)+ e (x)mod g (x)= e (x)modg(x), | (3.43) |
то есть величина остатка не зависит от того, какая комбинация была передана, а зависит лишь от того, какие произошли ошибки. Требования к производящим полиномам:
Во-первых,
|
, | (3.47) |
где р – целое число ;
, | (3.48) |
где - максимальная кратность гарантированно исправляемых ошибок, при этом кодовое расстояние . При это неравенство обычно обращается в равенство.
Во-вторых,
(3.49) |
для любого b (x), если и . Это значит, что многочлен g (x) является неприводимым (простым), то есть не делится без остатка ни на какой другой многочлен, кроме 1 и самого себя.
В-третьих,
, | (3.50) |
то есть двучлен делится без остатка на g (x) (сравните это с формулой (3.18)).
Кодирование в несистематическом виде:
s (x)= a (x) g (x), | (3.45) |
Для кодирования в систематической форме
. | (3.46) |
Операции, определяемые этим выражением, можно детализировать следующим образом:
1) умножение a (x) на означает, что k информационных символов сдвигается на r позиций вправо и в итоге занимают k старших (по степеням x) разрядов; r разрядов слева при этом оказываются нулевыми;
2) вычисляется r -разрядный остаток res(x) от деления полинома , соответствующего полученной таким образом комбинации;
3) эти r элементов остатка помещаются на r нулевых позиций комбинации, полученной в пункте 1, в качестве проверочных символов.
для кодирования/декодирования циклическим кодом не требуется использования производящей и проверочной матриц. Но матрицы существуют и имеют следующий вид:
, | (3.54) |
где - полином, согласованный с h (x), то есть коэффициенты этого полинома записаны в обратном порядке . Например, при n =7 для имеем .
Рассмотрим пример. код (7,4). производящий полином: .
Схема кодера, реализующего метод (3.45), приведена на рис. 3.3. Ячейки регистра обнуляются, затем при замкнутом ключе K в кодер вводятся 4 информационных символа, при этом в схеме вычисляются и выводятся 4 первых символа кодовой комбинации. Далее ключ K размыкается, и в течении следующих трёх тактов вычисляются и выводятся значения .
Схема кодера систематического кода, реализующая метод (3.46), дана на рис. 3.4.
Это схема деления полинома на полином g (x), но, в отличие
|
от схемы рис.2.11, она построена несколько иначе, поскольку ориентирована не на вычисление частного, а на вычисление остатка. Регистр обнуляется, переключатель П переводится в положение 2, и
в течение 4 тактов в кодер вводят 4 информационных символа. Одновременно эти символы поступают на выход в качестве информационной части кодовой комбинации (обратите внимание, что ввод и вывод производятся в обратном порядке, начиная с коэффициентов при старших степенях x). В это время в регистре с обратными связями начинается вычисление остатка. Затем переключатель П переводится в положение 1, отключая вход, и в течение следующих 3 тактов завершается вычисление остатка и его элементы выводятся на месте проверочных символов кодовой комбинации
Схема декодера, приведённая на рис. 3.5, также ориентирована на вычисление остатка от деления полинома v (x) на полином g (x). Регистр обнуляется, ключ K замыкается, и в течение 7 тактов в регистр вводятся 7 символов принятой комбинации, начиная с v 6 (старшего разряда). После завершения ввода в ячейках регистра оказывается записанным значение остатка res(x). Если res(x)=0 (в 3 ячейках регистра оказались нули), считают, что в принятой комбинации ошибок нет, и на этом декодирование заканчивается.
В противном случае , ключ К размыкается (фактически это соответствует ситуации, когда последующие входные символы равны нулю), и подают ещё 7 тактовых импульсов, формально продолжая процесс деления. Номер такта, на котором в ячейках регистра оказывается комбинация 100 (это случай res(x)=1, учитывается обратный порядок следования символов), и есть номер ошибочного символа. После этого исправление этого символа и отделение информационных символов – это тривиальные операции.
Чтобы не было сомнений, заметим, что ожидаемая комбинация 100 в течение 7 тактов обязательно появится, причём один раз. Дело в том, что при отключении входа схема рис. 3.5 превращается в генератор двоичной псевдослучайной М-последовательности с периодом (2.21) равным 7. Свойства М -последовательности таковы, что в течение периода в ячейках генератора обязательно по одному разу оказываются записанными все r -разрядные двоичные комбинации, кроме нулевой, разумеется.
Обратите внимание, что наличие сумматоров на стыках между ячейками регистра сдвига определяется значениями коэффициентов полинома g (x): сумматор есть, если , и он отсутствует, если . Таким образом, зная g(x), можно сразу составить схемы кодера и декодера для любого циклического кода (или схему генератора М-последовательности).
|
Как показывает практика, формальное запоминание приведённых соотношений и схем мало что даёт для понимания сути вопроса, если детально не разобрать хотя бы десяток конкретных численных примеров. В частности, если нужно закодировать информационную последовательность 0011, для которой , то, проследив такт за тактом работу схемы рис.3.4 и записывая содержимое ячеек, можно убедиться в том, что на выходе появится комбинация 1100010, которой соответствует полином (значение этого полинома вычислите отдельно по формуле (3.46) и сравните с комбинацией).
В заключение обязательно нужно отметить следующее обстоятельство. Благодаря циклическому свойству, при кодировании и декодировании циклического кода удаётся организовать конвейерную обработку длинных последовательностей символов в устройствах, содержащих удивительно малое количество простейших логических элементов. Например, для кода (255,247) кодер и декодер содержат по 8 ячеек регистра сдвига и по 4 сумматора по модулю 2. Благодаря этому ценному качеству среди всевозможных линейных блочных кодов именно циклические коды нашли наиболее широкое применение.
|
|
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
История создания датчика движения: Первый прибор для обнаружения движения был изобретен немецким физиком Генрихом Герцем...
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!