Теория кодирования (реализовать код Хэмминга)

[Zvezdochka]

Помогите разобраться с кодом Хэмминга. Необходимо написать программную реализацию на с++ кодера и декодера над полем многочленов. Вот абракадабра!

[Xaositect]

Что непонятно-то? Алгоритм у Вас есть?

[Zvezdochka]

Есть. В разных источниках по-разному. Какую книгу посоветуете? Я смотрела Блейхут и Яблонский. Там, да описан алгоритм, но там нет упоминания про многочлены. Может, скорее всего, я чего-то не догоняю

[Xaositect]

Так, слов "поле многочленов" я не заметил.
Вы уверены, что звучало именно "поле многочленов", а не "конечное поле" или что нибудь такое?

[Zvezdochka]

Циклический код над полем $F_2$. А кодовые слова - многочлены. Все равно ничего не понятно. С чего начать?

[Xaositect]

Каждое исходное слово $a = (a_0\dots a_m)$ и каждое кодовое слово $c = (c0\dots c_n)$ можно представлять многочленами над полем $\mathbb{F}_2$: $A(x) = \sum a_i x^i$ и $C(x) = \sum c_i x^i$.
Код называется циклическим, если для каждого кодового слова его циклический сдвиг также является кодовым словом. Можно доказать, что для циклического кода $C(x) = A(x)G(x) (\mod x^n-1)$. $G(x)$ называется порождающим многочленом, в случае кода Хэмминга это некоторый примитивный неприводимый многочлен.

Подробнее посмотреть можно, например, тут: http://www.codingtheory.gorodok.net/

-- Ср ноя 04, 2009 23:04:43 --

А насчет программной реализации можно еще посмотреть тут: http://yourtutor.narod.ru/cyclic/CyclicCodes.htm

[Zvezdochka]

Здорово. Спасибки, Вы просто волшебник. =)

[Zvezdochka]

Мне необходимо реализовать LFSR - линейный сдвиговый регистр с обратной связью над полем. А где можно узнать какой алгоритм? Какую литературу? Я смотрела книге Блейхут "Теория и практика кодов, контролирующих ошибки". Но там не понятно и не содержательно. Есть схема, но нет подробного описания алгоритма.

-- Пт ноя 13, 2009 03:32:35 --

Xaositect
Извините, что беспокою. Могли бы Вы мне помочь разобраться с одним из алгоритмов из теории кодирования?

[Xaositect]

Хмм.
Линейный регистр сдвига длины $n$ описывается уравнениями:
$z(t) = x_{0}(t)$ - идет на выход
$x_i(t+1) = x_{i+1}(t)$
$x_{n-1}(t+1) = \sum\limits_{i=0}^{n-1} \alpha_i x_i(t)$
В начальный момент времени регистр инициализируется произвольным ненулевым значением, например $(x_0,x_1,\dots,x_{n-1}) = (1,0,\dots,0)$
Для того, чтобы регистр имел максимально возможный период $2^n-1$ (так называемые m-последовательности), необходимо, чтобы полином $F(p) = p^n - \sum\limits_{i=0}^n \alpha_i p^i$ был примитивным. Таблицы примитивных полиномов можно найти.
Если регистр над полем $\mathbb{F}_2$, то все значения $x_i$ можно хранить в одном байте, а эти уравнения реализовать с помощью битовых операций. Например, один 16-битный регистр:

Используется синтаксис C

out = x&1;
new = ((x >> 0) ^ (x >> 2) ^ (x >> 3) ^ (x >> 5)) & 1;   // x_0 + x_2 + x_3 + x_5
x = (x >> 1) | (new << 15);
 

Это "Fibbonacci LFSR". Есть еще "Galois LFSR":
$z(t) = x_0(t)$
$x_{i}(t+1) = x_{i+1}(t)+\beta_i x_0(t)$
$x_{n-1}(t+1) = x_0(t)$
Тут коэффициенты $\beta_i$ "перевернуты": $\beta_i = n - 1 - \alpha_i$

Используется синтаксис C

out = x&1;
mask = out * 0b1011010000000000;   // x_0 + x_2 + x_3 + x_5
x = (x >> 1) ^ mask;
 

[Zvezdochka]

Код на С не ясен. Почему х0, х2, х3, х5? Еще арифметика поля. =( Ужас, а с ней как работать?

[Zvezdochka]

Кроме 0 - простые числа. Все равно не вижу логики. =(

[Xaositect]

Zvezdochka в сообщении #261708 писал(а):

Код на С не ясен. Почему х0, х2, х3, х5?

Потому что $p^{16} + p^5 + p^3 + p^2 + 1$ - примитивный многочлен над полем $\mathbb{F}_2$.

[Zvezdochka]

Эти три строчки реализуют регистр?

[Xaositect]

Zvezdochka в сообщении #261820 писал(а):

Эти три строчки реализуют регистр?

Один такт работы регистра.

[Zvezdochka]

Здравствуйте!
Вопрос по программе с линейным регистром сдвига. На вход алгоритму подается:
L - длина линейного регистра сдвига,
n - число необходимых выходов,
q - поле над которым выполняем вычисления - F_{q},
S[L] - массив с ненулевыми значениями, инициализирующие в начальный момент времени регистр,
a[L] - массив коэффициентов,
на выходе получим:
S[L](t) - t=1,2,...,n-1,n. Т.е. на выходе будут массивы линейного регистра сдвига в каждый момент времени t.
Но могли Вы мне объяснить на примере? Пусть:
L=5,
n = 2,
q = 4, то F_4, f(x)=x^2+x+1,
S[5]={1,0,0,0,0} - в 1-й момент времени, все предыдущие входные значения я выбирала произвольно, а вот массив а[5] тоже произвольно выбирается? Если да, то пусть
a[5]={0, 1,1, 1, 1}.
А теперь самое важное. Как вычислять выходные значения? По формуле $S[L](t+1) = \sum\limits_{i=0}^{L-1} a_i*S_i(t)$.
S[L](2)=1*0+0*1+0*1+0*1+0*1=0.
А как это связано с f(x)=x^2+x+1? На вход S подаются нули и единицы? или числа в десятичной системе? Выводить тоже в двоичной или в десятичной? Знаю, что Вам все это покажется простым, но мне не понятно. =( Объясните, пожалуйста, на примере. У меня так лучше получается. Спасибо.
--
С уважением, Юлдуз.