Прямое исправление ошибок с использованием коррекции стирания Рида-Соломона - PullRequest
Новая
       80

Прямое исправление ошибок с использованием коррекции стирания Рида-Соломона

1 голос
/ 18 февраля 2012

У меня есть задача кодировать и декодировать некоторые байты звука, используя метод контрольной суммы четности и Коррекция стирания Рида-Соломона .Я выполнил кодирование для первого метода (контрольной суммы четности), но мне нужна помощь для завершения второго метода, который заключается в обнаружении с помощью коррекции стирания Рида-Соломона.

На данный момент я знаю, что код RS добавляет t символов кk символов данных.Таким образом, он может найти и исправить до t/2 символов или, если места ошибок известны, так называемые стирания.Это может исправить до t.Для этой задачи я должен использовать поле Галуа GF (2 8 ) для представления каждого символа в виде байта.Операция сложения и вычитания основана на XOR.Таким образом, я должен использовать коды Рида-Соломона, которые способны исправлять до t=3 стираний.Вычисление одного кода Рида-Соломона теперь выполняется следующим образом: 

C<sub>0</sub> | C<sub>1</sub> |........| C<sub>k-1</sub> | C<sub>k</sub> | C<sub>k+1</sub> | C<sub>k+2</sub>

, поэтому байты кода можно рассматривать как вектор c=[c<sub>0</sub>,c<sub>1</sub>,...,c<sub>k+2</sub>], а один код C вычисляется из k байтов данных следующим образом d=[d<sub>0</sub>,d<sub>1</sub>,...,d<sub>k-1</sub>], поэтому мой процесс кодирования и декодирования требует следующую матрицу Вандермонда F 

1  1    1<sup>2</sup>     1<sup>3</sup>   ...   1<sup>k-1</sup>
1  2    2<sup>2</sup>     2<sup>3</sup>   ...   2<sup>k-1</sup>
             ...
1 k+2 (k+2)<sup>2</sup> (k+2)<sup>3</sup> ... (k+2)<sup>k-1</sup>
1 k+3 (k+3)<sup>2</sup> (k+3)<sup>3</sup> ... (k+3)<sup>k-1</sup>

, поэтому простое умножение вектора матрицы с использованием F & D дает C=F.D.

пока что я сделал для кодирования следующее: 

#else

void fox_encode(Buffer* bufin, Buffer* bufout, FoxEncData* algorithm_data){

    // Your encoder for Task 2.C.3 goes in here !!!

    while (bufin->size >= 1){
        guint8 databyte = bufin->data[0];       //Pick up a byte from input buffer
        buffer_push_byte (bufout, databyte);    //Send it 3 times
        buffer_push_byte (bufout, databyte);
        buffer_push_byte (bufout, databyte);
        buffer_pop (bufin, 1);                  //Remove it from the input buffer
    }
}

#endif

Мне нужен код для завершения этого кода для кодирования и декодирования моего класса fox_encode и fox_decode с использованием коррекции стирания Рида-Соломона.Буду признателен за любую помощь, чтобы выполнить эту задачу как можно скорее.

Заранее спасибо

Ответы [ 2 ]

0 голосов
/ 03 июля 2017

На Wikiversity теперь есть хороший учебник, в котором подробно описывается, как обрабатывать как стирание, так и ошибки.

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

  1. Вычислить синдромы. Затем проверьте, все ли это 0 коэффициентов, сообщение не нуждается в исправлении, иначе продолжите.
  2. Вызовите алгоритм Форни с синдромом и позициями стирания в качестве входных данных для вычисления полинома величины стирания (т. Е. Значений, которые нужно вычесть из полинома сообщения для получения исходного сообщения обратно).
  3. Вычтите message - erasure_magnitude_polynomial, чтобы восстановить исходное сообщение (если оно находится в пределах синглтона).

Помимо алгоритма Форнея, который может быть немного сложным, все остальные части очень просты и понятны. Действительно, самые сложные части, такие как алгоритм Берлекампа-Месси и поиск Чиена, необходимы только тогда, когда вы хотите декодировать ошибки, а вычисление синдромов Форнея необходимо только в том случае, если вы хотите исправить как стирания, так и ошибки (т.е. ошибки) Я читал статью, в которой описывается, что вычисление синдромов Форнея можно обойти, но я никогда не видел такого кода.

0 голосов
/ 06 января 2015

Вы можете взглянуть на мою C-реализацию RS (255,255-k), которая доступна на моей домашней странице .

Он обрабатывает как ошибки, так и стирания и исправляет любые шаблоны байтов ошибок / стираний, ограниченные:

(2 * errorCount + erasureCount) <= k. </p>

...