Возможность обнаружения ошибки Рида-Соломона не является 2T

Question

Я настраиваю библиотеку Рида-Соломона для исправления И обнаружения ошибок по мере их поступления. Для простоты давайте рассмотрим конфигурацию Рида-Соломона, где

m(symbol size)    : 8 [GF(256)]
k(user payload)   : 2
2T(parity symbols): 2

Yielding a transmitted payload of 4 octets.

Это может исправить любую ошибку в 1 символ иЦель этого поста, он может обнаружить 2 символа ошибки.Имеется ограниченная литература по обнаружению ошибок RS, однако только для краткого источника вы можете проверить введение в статье Википедии :

Добавив t контрольные символы к данным, код Рида-Соломона может обнаружить любую комбинацию до ошибочных символов включительно, или исправить до включительно символов ⌊t / 2⌋ включительно.

Однако это не похоже на моенаблюдения.

У меня есть библиотека, в основном построенная из этой статьи .

, который, насколько я могу судить, работает очень хорошо.Я установил исчерпывающий тест, связанный с нашей реализацией, и обнаружил случай, когда есть 2 ошибки символа (которые, как я понял, должны быть ОБНАРУЖЕНЫ), но это не так.Из того, что я понимаю, простая проверка, чтобы увидеть, произошла ли неисправимая ошибка, которая проходит обычные проверки (т. Е. Локатор ошибок действителен, обнаружение ошибок имеет допустимое количество ошибок, допустимая степень полинома) состоит в том, чтобы пересчитать синдромы дляисправленное сообщение.Если синдромы отличны от нуля, у нас все еще есть ошибка.Однако, когда я делаю это, все синдромы равны 0, что говорит о том, что ошибки не обнаружено, и что мы столкнулись между вектором ошибок с 1 ошибочным символом и вектором ошибки с 2 ошибочными символами.

Это тест:

# Create Message
msg_in = [0x10,0x2f]
# Append RS FEC codes
msg_enc = rs_encode_msg(msg_in)

# Apply Error
errVec = [0,0x2b,0,0xea]
for i,err in enumerate(errVec):
        msg[i] ^= err;

# Decode
# Syndromes
synd = rs_calc_syndromes(msg)
# Error Locator
err_loc = rs_find_error_locator(synd)
# Error Positions
pos = rs_find_errors(err_loc)
# Correct
msg = rs_correct_errata(msg, synd, pos, err_loc)

#Calculate syndromes again
newSynd = rs_calc_syndromes(msg)

Вывод:

Message
0x10 0x2f 

Encoded Message
0x10 0x2f 0x1 0x3e 

Encoded Message With Errors
0x10 0x4 0x1 0xd4

Syndromes
0xc1 0x46 
Error Locator
0x8 0x1
Error Position
0x00 # The first position

Corrected Message
0xd1 0x4 0x1 0xd4

Recalculated Syndromes
0x0 0x0

Если вы все еще читаете, спасибо.Я знаю, что не предоставил всю библиотеку, но я предоставил входные и выходные данные, а также значения ключевых переменных.Что я хочу знать, так это то, что мое понимание, написанное выше, неверно;что мы можем обнаружить ошибки 2T символов, где 2T - количество добавленных символов.Поскольку из этого контрольного примера кажется, что есть столкновение, я проверяю это далее, просто вычисляя синдромы по следующим векторам ошибок, которые дополнительно поддерживают столкновение, и что Рид Соломон НЕ МОЖЕТ ОБЯЗАТЕЛЬНО ОБНАРУЖИТЬ ВСЕ ошибки до 2T.Дайте мне знать, если я ошибаюсь.

error vector: 0xc1 0x0 0x0 0x0
yielding syndrome: 0xc1 0x46 

и

error vector: 0x0 0x2b 0x0 0xea
yielding syndrome: 0xc1 0x46 

Есть столкновение

Answer 1

С двумя символами четности синдромы будут уникальными только для ошибок одного символа, поэтому их можно использовать для исправления ошибок одного символа.В случае двухсимвольных ошибок синдромы будут ненулевыми (один из них может быть нулевым, но не обоим), но не всегда уникальным, для всех комбинаций двух местоположений ошибок и двух значений ошибок (именно поэтому два символаошибки не могут быть исправлены, если есть только два символа четности).

С двумя символами четности расстояние Хемминга составляет 3 символа.Каждое действительное (ноль синдромов == точное кратное полиному-генератору) кодовое слово отличается как минимум на 3 символа от любого другого действительного кодового слова, поэтому ни один из двухсимвольных ошибок не будет являться действительным (нулевой синдром) кодовым словом.

Для комбинации из 3 или более случаев ошибок можно найти синдромы == 0. Простейший пример этого - взять правильное кодовое слово (нулевое сообщение об ошибке) и xor полинома генератора 3 символов в любом месте.в сообщении, которое будет другим допустимым кодовым словом (точным кратным полиному генератора).

Кроме того, существует кодовое слово максимальной длины.Для типа BCH код Рида-Соломона, который вы используете, для GF (2 ^ n) это (2 ^ n) -1 символов.Если сообщение содержит 2 ^ n или более символов (включая символы четности), то два сообщения об ошибке с одинаковым значением ошибки в сообщении [i] и сообщении [i + 2 ^ n - 1] приведут к нулевым синдромам.Для исходного типа кода Рида-Соломона максимальная длина кодового слова составляет 2 ^ n (на один символ больше, чем у типа BCH), но он используется редко, поскольку декодирование работает со всем сообщением, а декодирование BCH - с синдромами.

---

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

Вероятность этого уменьшается, если кодовое слово сокращается, поскольку любое вычисленное местоположение, которое не находится в пределах диапазона сокращенного кодового слова, будет обнаруженной ошибкой.Если имеется n символов (включая символы четности), то вероятность ошибочного исправления одной ошибки на основе вычисленного местоположения в пределах диапазона составляет примерно n / 255.

В этом случае с кодовым словомразмером 4 байта я обнаружил 3060 из возможных 390150 двух случаев ошибки, при которых можно было бы создать правильное кодовое слово, выполнив единственное исправление ошибки, которое в итоге приведет к третьей ошибке.