 Популярные статьи | |
| Сейчас на сайте |  Гостей: 3
На сайте нет зарегистрированных пользователей
Пользователей: 9,955
новичок: Logyattella
|
|
| 2.4.7.1 Идея циклических кодов |
Любой групповой код может быть записан в виде матрицы, включающей k линейно независимых строк по n символов. Среди всего многообразия таких кодов можно выделить коды, у которых строки матрицы связаны дополнительным условием цикличности. Все строки матрицы такого кода могут быть получены циклическим сдвигом комбинации, называемой образующей для данного кода. Коды, удовлетворяющие этому условию, получили название циклических кодов.
Сдвиг осуществляется справа налево, причём крайний левый символ каждый раз переносится в конец комбинации. Запишем совокупность кодовых комбинаций, получающихся циклическим сдвигом комбинации 001011:
Число возможных циклических (n,k) –кодов, значительно меньше числа различных (n,k) групповых кодов. При описании циклических кодов n – разрядные кодовые комбинации представляются в виде многочленов фиктивной переменной х. Показатели степени у х соответствуют номерам разрядов (начиная с нулевого). Таким образом, образующую кодовую комбинацию 01011 можно записать так:
, (2.4.18)
или
. (2.4.19)
Наибольшую степень х в слагаемом с ненулевым коэффициентом называют степенью многочлена. Таким образом действия над кодовыми комбинациями сводятся к действиям над многочленами. Суммирование при этом осуществляется с приведением коэффициентов по модулю 2, а сдвиг образующего многочлена без переноса единицы в конец кодовой комбинации соответствует простому умножению на х. Например, умножив первую комбинацию 001011, соответствующую многочлену g0(x) = x3 + x + 1 на х, получим вторую строку матрицы 010110, соответствующую многочлену х*g0(x). Циклический сдвиг строки матрицы с единицей в старшем разряде равносилен умножению соответствующей строки многочлена на х с одновременным вычитанием из результата многочлена (х4 - 1), то есть с приведением по модулю (х4 + 1). Отсюда следует. Что любая разрешённая комбинация может быть получена в результате умножения образующего многочлена на некоторый другой многочлен с приведением результата по модулю (х4 + 1).
Иными словами, при соответствующем выборе образующего многочлена любой многочлен циклического кода будет делиться на него без остатка. Ни один многочлен, соответствующий запрещённой кодовой комбинации, на образующий многочлен без остатка не делится. Это свойство позволяет обнаружить ошибку. По виду остатка можно определить и вектор ошибки. Умножение и деление многочленов весьма просто осуществляется на регистрах сдвига с обратными связями, что и явилось причиной широкого применения циклических кодов.
Согласно определению циклического кода, все многочлены, соответствующие его кодовым комбинациям, должны делиться на g(x) без остатка. Для этого достаточно, чтобы на g(x) делились без остатка многочлены, составляющие образующую матрицу кода. Последние получаются циклическим сдвигом, что соответствует умножению g(x) на х с приведением по модулю (х4 + 1). Следовательно, в общем случае многочлен gi(x) является остатком от деления произведения g(x) *хi на х4 + 1, и может быть записан так:
, (2.4.20)
где с=1, если степень g(x) *хi превышает n-1, и с=0, если степень g(x) *хi не превышает n-1. Отсюда следует, что все многочлены матрицы, а поэтому и все многочлены кода будут делиться на g(x) без остатка только в том случае, если g(x) будет делиться без остатка на многочлен (х4 + 1). Таким образом, чтобы g(x) мог породить циклический код, он должен быть делителем многочлена (х4 + 1).
Если многочлен g(x) степени m=n-k является делителем многочлена (х4 + 1), то любой элемент кода делится на g(x) без остатка, либо в результате деления появляется остаток r(x), представляющий собой многочлен степени не выше m-1.
Групповой код способен исправить столько разновидностей ошибок, сколько различных классов насчитывается в приведённом разложении. Следовательно, корректирующая способность циклического кода будет тем выше, чем больше остатков может быть образовано при делении многочлена, соответствующего искажённой кодовой комбинации, на образующий многочлен кода. По заданному объёму кода однозначно определяется число информационных разрядов k. Далее необходимо найти наименьшее n, обеспечивающее обнаружение или исправление ошибок заданной кратности. В случае циклического кода эта проблема сводится к нахождению нужного многочлена g(x).
|
|
| Комментарии |
| Добавить комментарий |
|
Пожалуйста залогиньтесь для добавления комментария.
|
| Рейтинги |
|
Рейтинг доступен только для пользователей.
Пожалуйста, залогиньтесь или зарегистрируйтесь для голосования.
Нет данных для оценки.
|
|
| Гость |
Вы не зарегистрированны? Нажмите здесь для регистрации.
Забыли пароль? Запросите новый здесь.
|
| Мини-чат | Вам необходимо залогиниться.
Нет присланных сообщений.
|
|
