Синтез кодека кода Рида-Соломона
Содержание
Введение
. Выбор и обоснование кода
. Разработка кодека
.1 Синтез кодирующего устройства
.1.1 Разработка структурной схемы
кодера
.1.2 Разработка функциональной схемы
кодера
.1.3 Разработка принципиальной схемы
кодера
.2 Синтез декодирующего устройства
.2.1 Разработка структурной схемы
декодера
.2.2 Разработка функциональной схемы
декодера
.2.3 Разработка принципиальной схемы
декодера
Заключение
Литература
Введение
Передача данных является наиболее быстро
развивающейся областью техники. Достоверность получаемой информации играет
большую роль в жизни современного общества. Однако каналы передачи данных порой
содержат дефекты, влияющие на качество передаваемой информации, да и в работе
оборудования обработки информации иногда случаются сбои. По этой причине важную
роль приобретают механизмы детектирования ошибок. Ведь если ошибка обнаружена,
то можно осуществить повторную передачу данных и проблема будет решена.
Существуют помехоустойчивые коды Рида-Соломона
(РС-коды), широко использующихся в устройствах передачи и хранения данных для
обнаружения и исправления как одиночных, так и групповых ошибок. Область их
применения необычайно широка - кодеры и декодеры Рида-Соломона можно найти и в
ленточных запоминающих устройствах, и в контроллерах оперативной памяти, и в
модемах, и в жестких дисках, и в CD-ROM/DVD приводах и т. д. Благодаря ним
некоторые схемы архивного хранения данных безболезненно переносят порчу
нескольких секторов носителя, содержащего архив, а подчас - и полное разрушение
целого тома многотомного архива. Еще коды Рида-Соломона позволяют
восстанавливать байты, искаженные в результате сбоя программного или
аппаратного обеспечения.
1. Выбор и обоснование кода
В современных системах передачи,
обработки и хранения информации используется модульное (байтное) представление
информации. Обозначим передоваемое кодовое слово через А = (
), которое
под влиянием помех может исказиться и перейти в слово A*=(
). Вектор E=A* - A = (
), 
, i=1,2,…, n называется
словом-ошибкой. Далее будем считать, что длина кода n кратна b, т.е. n=b
m.
Одиночным модулем ошибок длиной b называется
слово-ошибка E=(), такое,
что символы с номерами i=kb + j, где k- целое
(0<k<n/b), j=1,2,…b могут быть
не равны нулю, в то время как все остальные символы 
заведомо
равны нулю.[1]
К основным параметрам РС - кодов,
корректирующих одиночные модули ошибок длиной 
=b двоичных
символов, относятся:
а) n=
(
+1) - длина
кодовой последовательности;
б) k=(-1) -
количество информационных символов, входящих в кодовую последовательность;
в) r=2 -
количество проверочных символов;
г) 
=n - k+1=2 -
минимальное кодовое расстояние;
д) P(x)= 
+
+…+x+1 -
образующий полином.
Кодирование информационного
сообщения Q(x)=
и
декодирование кодовых последовательностей F(x)=
осуществляется с помощью соответственно порождающей матрицы 
(x) и
проверочной матрицы 
(x), что в
общем виде можно записать так:
F(x) = Q(x)*G(x) -
кодирование информации,
S(x) = F(x)*H(x) -
декодирование информации.
Для того чтобы в процессе
кодирования Q(x) кодовые
последовательности F(x) получались
систематического вида, необходимо использовать каноническую порождающую
матрицу, т.е. матрицу вида (x)=[I:H], а также
использовать транспонированную проверочную матрицу, т.е. матрицу вида (x) = [
: I]. [2]
Проверочная матрица двухизбыточного
циклического РС-кода корректирующего одиночные модули ошибок кратностью двоичных
символов имеет следующее построение
H(x) =
, (1.1)
где 
=
- единичная матрица размерностью 
,
f=
.
При построении кодов, исправляющих
модуль ошибок длиной b, каждый модуль разрядов слова рассматривается как q-значный
разряд, принимающий одно из q-значений от 0 до (q-1). В этом
случае элементами столбцов в проверочной матрице являются подматрицы (0,1, 
), значения
которых определяются выражением:
, (1.2)
где 
- столбец, соответствующий остатку
от деления 
на
порождающий полином степени b; 
- показатель степени матрицы, 1
-1. В качестве порождающего полинома
используется неприводимый примитивный полином степени b, который
обеспечивает максимальное число различных матриц 
, равное -1. [1]
Проверочная матрица вида (1.1) может
быть преобразована путем нормализации, а именно путем перемножения каждого
элемента столбца матрицы на инверсию
его первого элемента, т.е. следующим образом:
. (1.3)
В этом случае проверочная матрица H(x) вида (1.1)
будет иметь следующее построение:
H(x) =
. (1.4)
Порождающая матрица G(x)
циклического РС-кода может быть построена по правилу:
(x)=[
], (1.5)
где 
- единичная подматрица размерностью
,
(x)
-транспонированная проверочная подматрица размерностью 
.
2. Разработка кодека
кодер
декодер кодек
Синтез структурных схем кодека циклического
РС-кода полностью определяется заданием параметров (n,
k, P(x),
q), количества и
кратности модулей ошибок, алгоритма декодирования и способа обработки
информации при кодировании. Далее выполним синтез структурных схем кодека
двоичного циклического РС - кода корректирующего одиночные модули ошибок
кратностью b=3 двоичных
символов при последовательном способе обработки информации и реализующего
синдромный алгоритм декодирования.
.1 Синтез кодирующего устройства
.1.1 Разработка структурной схемы кодера
Главной функцией кодера циклического
кода является формирование проверочных уравнений или проверок, правило
формирования которых может быть определено либо порождающей матрицей вида (x)=[I:H], либо
проверочной матрицей вида (x) = [: I].
Заданы следующие параметры РС-кода,
а именно:
n=27 двоичных
символов,
k=21 двоичных
символов.
Определим также еще несколько
параметров:
d0=n-k+1=27-21+1=7,
r=n-k=27-21=6
двоичных символов,
y=
- 1=23-1=7 -
количество подматриц вида.
Выбираем образующий полином вида P(x)=x3+x+1.
Следовательно, проверочная матрица
(1.4) будет иметь следующую структуру:
H(x)=
, (2.1)
где
=
, 
=
,
, 
,
, 
,
, 
,
где 
- остаток от деления на
примитивный полином
P(x) =
.
.
.
.
.
.
.
По полученным данным подматрицы 
проверочной
матрицы (2.1) имеют следующие структуры:
, 
, 
,
, 
, 
.
Следовательно, проверочная матрица
(2.1) кода Рида-Соломона с параметрами (27,21) будет иметь вид:
H(x) =
. (2.2)
Для синтеза структурной схемы необходимо
установить основные функции, выполняемые кодером.
Основными функциями кодера являются:
a)
Преобразование входной информации Q(x) из
последовательного кода в параллельный код;
б) Формирование проверочных
символов;
в) Формирование кодовой последовательности
F(x) путем
последо- вательного объединения k информационных символов и r=n-k проверочных
символов в единый кодовый поток.
Для реализации данных функций в
кодере необходимы следующие функциональные блоки:
КРИ-1/k (КРИ-1/21)
- коммутатор распределения входной информации на k (k=21)
подпотоков;
ФПСк - формирователь проверочных
символов кодера;
КОИ-n/1
(КОИ-27/1) - коммутатор объединения информации n (n=27)
параллельных подпотоков в единый поток;
ФСУ - формирователь сигналов
управления КОИ - 27/1;
ФТИ - формирователь тактовых
импульсов.
Для работы КРИ-1/21 и КОИ-27/1
используется соответственно формирователь тактовых импульсов (ФТИ) и
формирователь сигналов управления (ФСУ) коммутатора КОИ-27/1.
Обобщенная структурная схема кодера
РС-кода с параметрами (n, k)=(27,21)
представлена ниже (рисунок 1).
Рисунок 1.Структурная схема кодера
РС - кода
В соответствии с проверочной
матрицей вида (2.2) процесс кодирования информации РС-кодом можно записать так:
a1, a2, …, a21 -
информационные символы с выхода КРИ-1/21 поступают одновременно на
соответствующие входы КОИ-27/1 и на соответствующие входы ФПСк, который
формирует проверочные символы a22, a23, …, a27 по
следующим правилам:
a22=
a1+a4+a7+a10+a13+a16+a19,= a2+a5+a8+a11+a14+a17+a20,= a3+a6+a9+a12+a15+a18+a21,
a25= a1+a5+a7+a9+a10+a11+a13+a14+
a15+a17+a18+a21,= a2+a4+a6+a7+a8+a10+a11+a12+ a14+a15+a18+a19,=
a3+a4+a8+a10+a12+a13+a14+a16+ a17+ a18+a20+a21.
Сформированные шесть проверочных символов a22,
a23, …, a27
в параллельном коде поступают на соответствующие входы КОИ-27/1. С выхода
КОИ-27/1 последовательный код F(x)
поступает дальше в канал передачи данных.
.1.2 Разработка функциональной схемы кодера
Из алгоритма работы кодера следует, что принципы
построения его функциональных блоков могут быть приняты следующим образом:
а) КРИ-1/21 выполняется в виде последовательного
(RG1) и параллельного
(RG2) регистров
сдвига;
б) КОИ-27/1 выполняется в виде синхронного
мультиплексора;
в) ФПСк выполняется в виде совокупности
сумматоров по модулю два, входы которых подключаются к информационным цепям в
соответствии с проверочной матрицей (2.2);
г) ФСУ состоит из кольцевого двоичного счетчика
на двадцать семь;
д) ФТИ выполняется в виде кольцевого двоичного
счетчика на двадцать один.
На рисунке 2 представлена функциональная схема
кодера РС-кода (27.21).
Блок М2 - схема контроля четности, МХ - схема
мультиплексирования двадцати семи символов кодовой последовательности F(x).
2.1.3 Разработка принципиальной схемы кодера
Для построения принципиальной схемы кодера
необходимо выбрать элементную базу. Основным критерием выбора типа микросхемы
является тактовая частота, равная 100 МГц, на которой будет работать кодер.
Микросхема 74АСТ164M
представляет собой 8-разрядный сдвиговый регистр с последовательной загрузкой и
параллельной выгрузкой. Максимальная тактовая частота данной микросхемы равна
115 МГц.
Рисунок 2.Функциональная схема
кодера РС - кода.
Микросхема 74AСT373SC
представляет собой 8-разрядный буферный регистр. Максимальная тактовая частота
данной микросхемы равна 150 МГц.
Микросхема 74ACT163SC -
4-разрядный двоичный счетчик. Максимальная тактовая частота данной микросхемы
равна 160 МГц.
Микросхема 74ACT08DC - 4
элемента 2И. Максимальная тактовая частота данной микросхемы равна 150 МГц.
Микросхема 74ACТ280QC -
9-разрядная схема контроля четности/ нечетности. Максимальная тактовая частота
данной микросхемы равна 120 МГц.
Микросхема 74ACT251SC -
восьмивходовой селектор-мультиплексор. максимальная тактовая частота - 150 МГц.
Все микросхемы изготовлены
американской фирмой NSC.
Принципиальная схема кодера
представлена в приложении А.
.2 Синтез декодирующего устройства
.2.1 Разработка структурной схемы
декодера
Для синтеза структурной схемы
циклического РС-кода, реализующего синдромный алгоритм декодирования,
необходимо определить основные функции декодера. Основными функциями декодера
являются:
распределение символов кодовой
последовательности F’(x) на
двадцать семь (n=27) параллельных подпотоков a’1, a’2,…, a’27, знак
(’) означает, что данные символы приняты с определенной степенью их
достоверности;
формирование проверочных символов a’’22, a’’23,…, a’’27 по
алгоритму аналогично используемому в кодере;
формирование синдромных символов S1, S2,…, S6 по
правилу:
S1=a’22+a’’22;
S4=a’25+a’’25;=a’23+a’’23; S5=a’26+a’’26;=a’24+a’’24; S6=a’27+a’’27;
- формирование частных синдромов;
- сравнение синдромных символов и
символов частных синдромов;
коррекция ошибочных информационных
символов;
объединение символов 21-го
информационных подпотоков в информа-ционный поток и выдача сообщения Q(x)
получателю.
Для реализации данных функций в декодере
необходимы следующие функциональные блоки:
КРИ-1/n
(КРИ -1/27) - коммутатор распределения информации на n
(n=27) параллельных
подпотоков;
КОИ-k/1
(КОИ-21/1) - коммутатор объединения информации k
(k=21) параллельных
подпотоков в последовательный поток;
ФПСд - формирователь проверочных символов
декодера;
ФСС - формирователь синдромных символов;
БВЧС - блок вычисления частных синдромов;
БСС - блок сравнения синдромных символов и
символов частных синдромов;
БКО - блок коррекции ошибок;
АС - анализатор синдрома;
ФСУ КОИ-27/1 - формирователь сигналов управления
(КОИ-27/1).
В соответствии с составом функциональных блоков
декодера и последовательностью выполняемых функций структурная схема декодера
будет иметь следующее построение (рисунок 3.).
Декодер работает следующим образом. Кодовые
символы a’1, a’2,…,
a’27 принятой
кодовой последовательности F’(x)
поступают на вход КРИ-1/27, где распределяются на двадцать семь параллельных
подпотоков, двадцать один из которых - информационные символы (a’1,
a’2,…, a’21)
и шесть подпотоков - проверочные символы (a’22,a’23,…,a’27).
Принятые информаци-онные символы поступают одновременно на соответствующие
входы БКО и ФПСд, формирующий проверочные символы a’’22,
a’’23, …, a’’27,
которые поступают в параллельном коде на соответствующие входы ФСС, на другие
входы которого поступают принятые проверочные символы a’22,
a’23,…, a’27.
ФСС формирует шесть синдромных символов S1,…,
S6. Синдромные
символы S1, S2,
S3 поступают
одновременно на соответствующие входы БВЧС и АС, а синдромные символы S4,
S5, S6
поступают на соответствующие входы БСС.
Рисунок 3. Структурная схема
декодера РС-кода.
Анализ проверочной матрицы (2.2)
показывает, что конфигурация возможных ошибок в модуле равна синдрому {S1*}, который
определяется верхней половиной проверочной матрицы, а местоположение модуля
ошибок равно синдрому {S2*}, который определяется нижней
половиной проверочной матрицы.
БВЧС реализует операцию умножения,
синдрома {S1*} на
транспонированную подматрицу
(
), где i=0,1,…,6,
т.е.{
j}={S1*}*,
где {S1*}=
, j=1,2,…,7.
Если 
j={S2*}=
, то
значение j определяет
номер (позицию) всех семи частных синдромов:
1=*
= (S1, S2, S3), 
5=*
= (S1+S3,
S1+S2+S3, S1+S2),
2=*
= (S2+S3, S1, S2), 6=*
= (S3,
S1+S3, S1+S2+S3),
3=*
= (S1+S2, S2+S3, S1), 7=*
= (S2, S3,
S1+S3).
4=*
= (S1+S2+S3, S1+S2, S2+S3),
В БСС производится сравнение
полученных выше частных синдромов {1,…, 7} с синдромом {S2*}. Если j={S2*}, то
обнаружен модуль ошибок с номером j.
АС формирует вектор коррекции модуля
ошибок путем анализа синдромных символов S1, S2, S3.
.2.2 Разработка функциональной схемы
декодера
Из алгоритма работы декодера следует, что
принципы построения его функциональных блоков могут быть приняты следующим
образом:
КРИ-1/27 выполняется в виде последовательного (RG1)
и параллельного (RG2)
регистров сдвига;
КОИ-21/1 выполняется в виде синхронного
мультиплексора;
ФПСд выполняется в виде совокупности сумматоров
по модулю два, входы которых подключаются к информационным цепям в соответствии
с проверочной матрицей (2.2);
ФСУ состоит из кольцевого двоичного счетчика на
двадцать один;
ФТИ выполняется в виде кольцевого двоичного
счетчика на двадцать семь;
ФСС, БВЧС выполняются в виде схем контроля
четности;
БСС состоит из схем контроля четности и
логических элементов И-НЕ.
Представим отдельные функциональные блоки
декодера. На рисунке 4 показан ФПСд.
Рисунок 4.Блок ФПСд
На рисунке 5 представлена схема
блока ФСС. Данный блок осуществляет попарное сложение по модулю два символов a’’22, a’’23, …, a’’27 и a’22, a’23,…, a’27. На
выходе данного блока формируются синдромные символы S1,…, S6.
Рисунок 5. Блок ФСС
На рисунке 6 представлена
функциональная схема БВЧС.
Рисунок 6. Функциональная схема БВЧС
На рисунке 7 представлена
функциональная схема БСС.
Рисунок 7. Функциональная схема БСС.
На рисунке 8 представлена схема
блока АС.
Рисунок 8. Функциональная схема
блока АС.
На рисунке 9 представлена
функциональная схема БКО.
Рисунок 9. Функциональная схема БКО.
.2.3 Разработка принципиальной схемы
декодера
Для построения принципиальной схемы
декодера необходимо выбрать элементную базу. Основным критерием выбора типа
микросхемы является тактовая частота, равная 100 МГц, на которой будет работать
декодер.
Микросхема 74АСТ164M
представляет собой 8-разрядный сдвиговый регистр с последовательной загрузкой и
параллельной выгрузкой. Максимальная тактовая частота данной микросхемы равна
115 МГц.
Микросхема 74AСТ373SC
представляет собой 8-разрядный буферный регистр. Максимальная тактовая частота
данной микросхемы равна 150 МГц.
Микросхема 74ACT163SC -
4-разрядный двоичный счетчик. Максимальная тактовая частота данной микросхемы
равна 160 МГц.
Микросхема 74ACT08DC - 4
элемента 2И. Максимальная тактовая частота данной микросхемы равна 150 МГц.
Микросхема 74ACТ280QC -
9-разрядная схема контроля четности/ нечетности. Максимальная тактовая частота
данной микросхемы равна 120 МГц.
Микросхема 74ACТ86PM - 4 двухвходовых
логических элемента ИСКЛЮЧАЮЩЕЕ ИЛИ. Максимальная тактовая частота данной
микросхемы равна 160 МГц.
Микросхема 74АСТ4002M - 2
логических элемента 4ИЛИ-НЕ. Максимальная тактовая частота данной микросхемы -
100 МГц.
Микросхема 74ACT251SC - восьмивходовой
селектор-мультиплексор. максимальная тактовая частота - 150 МГц.
Все микросхемы изготовлены
американской фирмой NSC.
Принципиальная схема кодера
представлена в приложении Б.
Заключение
В данной курсовой работе разработаны
кодер и декодер кода Рида-Соломона с параметрами (27, 21). В результате
проделанный вычислений получили, что данный РС-код позволяет исправлять
одиночную модульную ошибку для модуля длиной в три символа. К достоинствам
разработанного кодека можно отнести следующее:
а) простота реализации алгоритмов
кодирования и декодирования на логических элементах;
б) Достаточная высокая скорость
обработки закодированной информации.
Недостатком разработанного кодека
можно считать наличие избыточного числа элементов в схемах.
Литература
1. Теория прикладного кодирования. В
2 т.Т 2/ В.К. Конопелько, В.А. Липницкий, В.Д. Дворников и др. - Мн.: БГУИР,
2004, - 398с.
. Королев А.И. Коды и устройства
помехоустойчивого кодирования информации. - Мн.: БГУИР, 2010, - 286с.