Расшифровка логики большинства - Majority logic decoding

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

Теория

В двоичном алфавите, состоящем из ${ displaystyle 0,1}$ , если ${ Displaystyle (п, 1)}$ используется код повторения, затем каждый входной бит отображается на кодовое слово как строка ${ displaystyle n}$ -реплицированные входные биты. В общем ${ displaystyle n = 2t + 1}$ , нечетное число.

Коды повторения могут обнаруживать до ${ Displaystyle [п / 2]}$ ошибки передачи. Ошибки декодирования возникают, когда возникает больше, чем этих ошибок передачи. Таким образом, предполагая, что ошибки передачи битов независимы, вероятность ошибки для кода с повторением определяется выражением ${ displaystyle P_ {e} = sum _ {k = { frac {n + 1} {2}}} ^ {n} {n choose k} epsilon ^ {k} (1- epsilon) ^ {(nk)}}$ , куда ${ displaystyle epsilon}$ это ошибка по каналу передачи.

Алгоритм

Предположение: кодовое слово ${ Displaystyle (п, 1)}$ , куда ${ displaystyle n = 2t + 1}$ , нечетное число.

Рассчитайте ${ displaystyle d_ {H}}$ Вес Хэмминга кода повторения.
если ${ displaystyle d_ {H} leq t}$ , декодировать кодовое слово, чтобы все нули
если ${ displaystyle d_ {H} geq t + 1}$ , декодировать кодовое слово как все единицы

Этот алгоритм сам по себе является логической функцией, функция большинства.

Пример

В ${ Displaystyle (п, 1)}$ код, если R = [1 0 1 1 0], то он будет декодирован как,

${ Displaystyle п = 5, т = 2}$ , ${ displaystyle d_ {H} = 3}$ , поэтому R '= [1 1 1 1 1]
Следовательно, бит переданного сообщения был 1.

Расшифровка логики большинства - Majority logic decoding

Содержание

Теория

Алгоритм

Пример

Рекомендации