WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 || 3 |

Во второй главе «Недвоичный многопороговый декодер» рассмотрен недвоичный многопороговый алгоритм декодирования, описаны модификации qМПД для его использования в каналах со стираниями и в каналах со стираниями и искажениями, получены экспериментальные характеристики qМПД в каналах Гилберта-Эллиота с пакетирующимися ошибками, в каналах со стираниями и в каналах со стираниями и искажениями.

Недвоичный многопороговый декодер (qМПД) является простейшим декодером мажоритарного типа. qМПД используется для декодирования недвоичных самоортогональных кодов (СОК). Пример схемы qМПД блокового недвоичного СОК, заданного образующим полиномом g(x) = 1+ x + x4 + x6, представлен на рисунке 1.

Рисунок 1 – Пример схемы qМПД блокового недвоичного СОК Процедура декодирования qМПД заключается в том, что для очередного контролируемого недвоичным пороговым элементом (qПЭ) информационного символа кода uj происходит подсчет количества и определение значений двух относящихся к нему и наиболее часто встречающихся проверок кода, например, b1 и b2, причем b1 встречается m1 раз, b2 – m2 раз (m1m2), а остальные значения проверок для декодируемого символа uj встречаются не более m2 раз. Если разница m1–m2 будет больше значения порога T, то на выходе qПЭ будет значение b1, которое вычитается из соответствующих элементов синдромного регистра, из текущего элемента информационного регистра и заносится в связанный с информационным элемент разностного регистра. Если окажется, что два наиболее часто встречающихся значения проверок таковы, что m1=m2, то выход qПЭ устанавливается равным нулю, т. е. символ uj не изменяется, и делается попытка декодирования любого другого информационного символа кода.

До настоящего времени были известны характеристики qМПД только для q-ичных симметричных каналов, где ошибки появлялись независимо друг от друга с равной вероятностью. Однако часто в реальных системах передачи и хранения информации возникают пакеты ошибок, которые обычно существенно ухудшают эффективность классических методов коррекции ошибок. Для описания таких каналов подходит модель канала Гилберта-Эллиота. Поэтому в диссертационной работе были проведены исследования эффективности qМПД в этих более сложных условиях. Результаты такого исследовании показали, что qМПД для кода с R=1/2, n=32000 и q=256 эффективно исправляет около 25% ошибок в данном канале, а декодер кодов Рида-Соломона длиной 255 однобайтовых символов – только 1% ошибок.

Типичными представителями каналов с пакетирующимися ошибками являются системы хранения данных. Например, для защиты информации, находящейся на DVD дисках, используются коды произведения Рида– Соломона с R=7/8 длиной n38000. Во второй главе диссертации были подобраны недвоичные СОК с аналогичными параметрами, обладающие существенно лучшими корректирующими способностями.

Часто в системах передачи и хранения данных для дополнительного повышения эффективности декодирования ненадежные символы отмечаются как стертые. В дальнейшем восстановить стертые символы оказывается значительно проще, чем исправлять ошибки.

Работа qМПД, способного исправлять стирания, в таком канале отличается от работы в q-ичном симметричном канале тем, что при вычислении символов синдрома стертые информационные и проверочные символы на значение проверок не влияют, но при этом для каждой проверки запоминается число участвующих в его формировании стираний. Затем в процессе декодирования стертого информационного символа среди относящихся к нему проверок ищется проверка, содержащая только одно стирание. Очевидно, что это стирание будет вызвано декодируемым информационным символом, который по значению данной проверки может быть легко восстановлен.

На рисунке 2 представлены зависимости вероятности невосстановления символа на выходе декодера от вероятности стирания в канале.

Здесь показаны характеристики декодера кодов Рида-Соломона и qМПД для кодов с R=1/2. Из рисунка видно, что эффективность qМПД при существенно меньшей сложности реализации превосходит эффективность практически реализуемого декодера кодов Рида-Соломона длиной 255 однобайтовых символов.

Рисунок 2 – Характеристики qМПД и декодера кодов РС в каналах со стираниями Также в диссертационной работе были проведены исследования возможности использования qМПД в каналах со стираниями и искажениями, в которых, в отличие от каналов со стираниями, возможно появление ошибочных символов. Канал со стираниями и искажениями характеризуется тем, что символы по нему передаются правильно с вероятностью 1–Pc–P0, «стираются» с вероятностью Pc и искажаются с вероятностью P0.

При работе в таком канале qМПД на каждой итерации декодирования должен уметь исправлять как стирания, так и ошибки. Процедура исправления ошибок в этом случае полностью аналогична исправлению ошибок для q-ичного симметричного канала, а при декодировании стираний решение о значении восстанавливаемого символа по одной проверке вынести уже нельзя, поскольку проверка может быть ошибочной из-за возможных искажений в канале. Поэтому при декодировании стертого символа сначала среди проверок относительно данного символа ищутся все проверки, содержащие только по одному стиранию. Затем по каждой из них определяется значение стертого символа, после чего принимается окончательное решение о значении декодируемого символа по большинству голосов.

Также во второй главе оценена нижняя граница вероятности ошибки декодирования для рассматриваемого qМПД в таком канале. Для этого были выписаны наиболее частые события, которые всегда приводят к ошибкам оптимального декодера недвоичных СОК, и определены вероятности появления этих событий:

1. Все проверочные символы и информационный символ стерты:

P1 = Pcd.

2. Информационный символ стерт, один проверочный символ принят правильно, один проверочный символ ошибочен, остальные проверочные символы стерты:

P2 = P0 (1- Pc - P0 ) Pcd -2 (d -1) (d - 2).

3. Информационный символ ошибочен, один проверочный символ принят правильно, остальные проверочные символы стерты:

P3 = P0 (1- Pc - P0 ) Pcd -2 (d -1) 4. Информационный символ стерт, один проверочный символ ошибочен, остальные проверочные символы стерты:

P4 = P0 Pcd -1 (d -1).

5. Информационный символ стерт, два проверочных символа ошибочны, один проверочный символ принят правильно, остальные проверочные символы стерты:

(d -1) (d - 2) (d - 3) P5 = P02 (1- Pc - P0 ) Pcd -3.

Нижняя оценка вероятности символьной ошибки оптимального декодирования определяется суммой найденных выше вероятностей:

Ps =. (1) P i i=Результаты исследования возможности использования qМПД в каналах со стираниями и искажениями показали, что характеристики qМПД в области эффективной работы сопоставимы с характеристиками декодера кодов Рида-Соломона. Подчеркнем, что при этом qМПД оказывается более чем в 30 раз проще для практической реализации. Также отметим, что нижняя оценка (1) оказывается достаточно точной для предварительного оценивания характеристик qМПД, способного исправлять ошибки и восстанавливать стирания.

В третьей главе «Алгоритмы улучшения характеристик qМПД» приводятся алгоритмы, применение которых позволяет ускорить работу и повысить эффективность декодирования qМПД; разработаны каскадные схемы коррекции ошибок на базе qМПД, позволяющие улучшить характеристики qМПД в области его эффективной работы.

Несмотря на то, что скорость работы qМПД во много раз превосходит скорость работы других недвоичных декодеров, существует возможность дополнительного ускорения работы qМПД. Среди элементов qМПД наибольшую сложность имеет недвоичный пороговый элемент (qПЭ). В диссертационной работе предложен новый алгоритм работы порогового элемента, позволяющий существенно ускорить работу qМПД. На основании данной идеи была разработана схема модифицированного qМПД, представленная на рисунке 3. Отметим, что в эту схему вводится дополнительный регистр, элементы которого показывают, нужно ли заново обрабатывать информацию, поступающую на пороговый элемент с синдромного и разностного регистров. При этом, так как на различных итерациях может измениться значение порога qПЭ, то необходимо запоминать значение разности m1–m2 и значение b1 наиболее популярной проверки, которое используется при срабатывании qПЭ.

Рисунок 3 – Модифицированный qМПД недвоичного СОК Процедура декодирования принятого сообщения модифицированным qМПД состоит в следующем:

1. Произвольно выбирается декодируемый информационный символ uj принятого сообщения.

2. Если элемент регистра признаков пересчета, соответствующий информационному символу uj, равен 1, то подсчитывается число двух наиболее часто встречающихся проверок. Значения этих двух проверок равны b1 и b2, а их количество равно m1 и m2 соответственно, причем m1m2. Если элемент регистра признаков пересчета равен 0, то значение разности m1–mустанавливается равным значению текущего элемента порогового регистра, а значение b1 – значению текущего элемента регистра коррекций.

3. Если m1–m2T, то устанавливается в 0 значение элемента регистра признаков пересчета, соответствующего информационному символу uj, в текущий элемент порогового регистра заносится разность m1–m2, в текущий элемент регистра коррекций – значение b1. Если m1–m2>T, то из uj, dj и всех проверок относительно uj вычитается оценка ошибки, равная b1. Также устанавливаются в 1 все элементы регистра признаков, соответствующие информационные символы которых участвовали в формировании измененных символов синдромного регистра.

4. Осуществляется переход к новому произвольному um, mj и далее переход к пункту 2.

Для большего выигрыша по объему операций данную модификацию qМПД в некоторых случаях следует применять после нескольких обычных итераций декодирования. Использование предложенного алгоритма позволяет в 2-3 раза ускорить работу qМПД, при этом эффективность декодирования по сравнению с обычным qМПД остается без изменений.

Для того чтобы qМПД показывал высокую эффективность, необходимо уделить большое внимание выбору используемых кодов. Как известно лучшими недвоичными СОК являются коды с параллельным кодированием с несколькими информационными и проверочными ветвями. При этом чрезвычайно трудоемкой задачей является определение количества символов информационной ветви, участвующих в формировании символов каждой проверочной ветви. Для решения этой задачи был предложен алгоритм, позволяющий строить наиболее эффективные самоортогональные коды для схем параллельного кодирования. На рисунке 4 представлена схема данного алгоритма.

Рисунок 4 – Алгоритм построения недвоичных СОК Здесь poly[][][] – полином, определяющий недвоичный СОК;

poly[i][j][0] – определяет количество символов i-й информационной ветви, участвующих в формировании символов j-й проверочной ветви; min[i][j] – минимальное количество символов i-й информационной ветви, участвующих в формировании символов j-й проверочной ветви; max[i][j] – максимальное количество символов i-й информационной ветви, участвующих в формировании символов j-й проверочной ветви; GetProb(poly) – функция для определения вероятности ошибки на выходе qМПД для недвоичного СОК, заданного полиномом poly.

Результаты моделирования недвоичных параллельных СОК в qСК показаны на рисунке 5. На рисунке видно, что область эффективной работы параллельного недвоичного СОК с R=1/2, полученного с помощью применения данного алгоритма, оказывается на 13% ближе к пропускной способности канала по сравнению с лучшими из известных недвоичных СОК. Область эффективной работы параллельного кода с R=7/8 оказывается на 20% ближе к пропускной способности канала.

Рисунок 5 – Результаты моделирования параллельных СОК в qСК Из теории кодирования известно, что использование каскадных схем коррекции ошибок позволяет повысить эффективность применения кодирования по сравнению с базовыми некаскадными методами. В третьей главе диссертации рассмотрены вопросы применения qМПД в составе каскадных схем кодирования. Рассмотрена известная каскадная схема, состоящая из недвоичного самоортогонального кода и кода контроля по модулю q. Для данной каскадной схемы сформулирована и доказана следующая теорема.

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

Предложена новая каскадная схема кодирования, состоящая из недвоичного СОК и модифицированного недвоичного кода Хэмминга.

Обычные недвоичные коды Хэмминга используют вычисления в полях Галуа, что является сложным для реализации при большом размере символа. Поэтому на базе обычных кодов Хэмминга были построены модифицированные недвоичные коды Хэмминга, которые используют только операции сложения и вычитания целых чисел по модулю q. Декодер таких кодов всегда исправляет одну ошибку и в большинстве случаев две ошибки в блоке. Процент блоков с двумя ошибками, исправляемых декодером модифицированных недвоичных кодов Хэмминга:

- 3 2m + 3m+ 100%, где m – количество проверочных символов в 14m кодовом слове. Например, для m=8 исправляется порядка 71% блоков с двумя ошибками.

Процент блоков с двумя ошибками, исправляемых декодером модифицированных недвоичных расширенных кодов Хэмминга:

((q - 2) / q) 100%. Например, для q=256 исправляется порядка 99.2% блоков с двумя ошибками, а при q=65536 исправляется порядка 99.997% блоков с двумя ошибками.

Получена нижняя оценка вероятности ошибки на выходе каскадной схемы, состоящей из qМПД и декодера модифицированного недвоичного кода Хэмминга:

Nh-(13m+1 - 3 2m +1 PS ) PS3(Nh -1)(Nh - 2) Nh-Perr = (1- PS ) PS2 (Nh -1) +, 4m где PS – оценка вероятности ошибки на выходе qМПД, Nh = 2m -1 – длина блока недвоичного кода Хэмминга Получена нижняя оценка вероятности ошибки на выходе каскадной схемы, состоящей из qМПД и декодера модифицированного недвоичного расширенного кода Хэмминга:

Nexth-2 Nexth-2 (1- PS ) PS2(Nexth -1) (1- PS ) PS3(Nexth -1)(Nexth - 2) PerrExt = +, q где Nexth = 2m – длина блока недвоичного расширенного кода Хэмминга.

На рисунке 6 представлены характеристики каскадных схем кодирования, состоящих из недвоичного СОК и недвоичных кодов Хэмминга.

Из рисунка видно, что применение совместно с qМПД в области его эффективной работы декодеров модифицированных недвоичных кодов Хэмминга позволяет снизить вероятность ошибки на выходе каскадной схемы на три и более порядков.

Pages:     | 1 || 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»