.

VHDL-модель устройства обнаружения и коррекции ошибок кодом рида-соломона на базе плис

Язык: русский
Формат: реферат
Тип документа: Word Doc
2 1602
Скачать документ

Реферат на тему:

VHDL-модель устройства обнаружения и коррекции ошибок кодом
рида-соломона на базе плис

 

В данной работе рассмотрена аппаратная реализация устройства
обнаружения и коррекции ошибок кодом Рида-Соломона. Для реализации
алгоритма функционирования устройства выбран язык VHDL. Для визуализации
результатов работы проведено функциональное моделирование с помощью
инструментального средства Active-HDL 4.0. Проведен синтез
принципиальной схемы, в результате чего получен файл отчета, содержащий
данные о процессе синтеза, этапах размещения и трассировки.

 

Введение

Большие объемы данных в современных системах связи и хранение данных,
большинство из которых чувствительны к ошибкам, приводят к необходимости
контроля ошибок (1).

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

В данной работе разработан кодер, декодер основанный на алгоритме работы
кода Рида–Соломона, обнаруживающего двухпакетные и исправляющего
однопакетные ошибки, возникающие при передаче по линии связи. При
фиксированных длине кода (n) и количестве информационных разрядов (k) не
существует кода, у которого минимальное расстояние больше, чем у кода
Рида-Соломона. Этот факт является веским основанием для использования
кода Рида-Соломона. Коды Рида-Соломона всегда оказываются короче всех
других кодов над тем же алфавитом (1).

1 Математические основы кода Рида-Солмона.

1.1 Проверочная Н-матрица кода Рида-Соломона.

При построении кодов, исправляющих пакетные ошибки с разрядностью b,
пакет разрядов слова рассматривают как q- значный разряд, принимающий
одно из q значений от 0 до q-1. В этом случае в Н-матрице элементами
столбцов являются не 0 и 1, а подматрицы 0,1,hk .

Длина кода n, а количество контрольных разрядов r

n=b*(2b+2 ), r=3*b ( 1.1 )

При разрядности пакета b=4 H-матрица модифицированного кода
Рида-Соломона, обнаруживающего двойные и исправляющего одиночные пакеты
ошибок имеет вид:

    I I I I I I I I I I I I I I I I 0 0

H = I h1 h2 h3 h4 h5 h6 h7 h8 h9 h10 h11 h12 h13 h14 0 I 0

  I h2 h4 h6 h8 h10 h12 h14 h1 h3 h5 h7 h9 h11 h13 0 0 I

    l1                           l15 с3   c1

В проверочной матрице l1…l15 – пакеты информационных разрядов,
с3…с1-пакеты контрольных разрядов. Длина кода n=72, количество
информационных разрядов k=60 (согласно 1.1).

При разрядности пакета b=4 матрицы hk имеют следующий вид:

Матрица h15 является единичной и обозначается как I. За нулевую
принимается матрица, элементы которой равны нулю.

1.2 Кодирование и декодирование кода Рида-Соломона.

Кодирование осуществляется путем добавления к передаваемой информации
контрольных разрядов. Контрольные разряды вычисляются на основе
проверочной Н–матрицы. Каждый контрольный разряд равен сумме по модулю
два информационных разрядов, которым соответствуют единицы в
соответствующей строке Н – матрицы.

Декодирование кода Рида-Соломона рассмотрено на примере
модифицированного кода. Чтобы определить ошибку в сообщении, необходимо
вычислить 12 синдромов. Каждый синдром равен сумме по модулю два
информационных разрядов, которым соответствуют единицы в соответствующей
строке Н–матрицы и соответствующего контрольного разряда.

При нулевом значении синдрома ошибка отсутствует. Если возникла ошибка в
одном из пакетов разрядов считанного сообщения, то значение синдрома не
равно нулю.

Так как третья (верхняя) строка Н-матрицы содержит единичные подматрицы,
то пакет разрядов синдрома S3 будет содержать единицы в разрядах,
соответствующих отказавшим разрядам пакета. Если ошибка сосредоточена в
пределах одного пакета, соответствующего матрице hk, то между значениями
синдромов S1…S3 существует связь, определяемая видом матрицы hk. При
появлении двух пакетов ошибок эта связь нарушается.

Если отказ возник в разрядах i-го пакета, то ошибка может быть
представлена в виде 0…0е0…0, где е-двоичный символ, равный единице при
наличии ошибки в соответствующем разряде и нулю-при ее отсутствии;
0-двоичный символ.

Синдромы определяются по следующим формулам:

eT, ( 1.2)

где hi1, hi2, hi3-соответственно подматрицы первой, второй, третьей
строки Н-матрицы для i-го пакета; еТ-матрица-столбец, обозначающая
ошибку.

Учитывая, что hi3 –единичная матрица

S3=eT, S2=hi2*S3 , S1=hi1*S3или S2+hi2*S3=0, S1+hi1*S3=0. (1.3)

Система (1.3) является индикатором ошибок в i-м пакете. Если синдромы
S1,S2,S3 получены из-за ошибки в одном информационном пакете разрядов,
то равенства (1.3) выполняются для данного пакета.

Пользуясь системой (1.3) найдены предполагаемые ошибки во всех пакетах
считанного слова.

Неисправен первый пакет:

S2+I*S3=0, S1+I*S3=0 (1.4)

S21

S22

S23

S24 + 1000

0100

0010

0001 * S31

S32

S33

S34 = 0

0

0

0

(1.5)

 

S11

S12

S13

S14 + 1000

0100

0010

0001 * S31

S32

S33

S34 = 0

0

0

0

 

 

(1.6)

 

 

 

где S1i,Si2,S3i-значения i-го разряда первого, второго, третьего
4-разрядного синдрома соответственно. Произведя матричное умножение
выражений (1.5) и (1.6), получаем

S34=0. (1.7)

S34=0.

Аналогично определяются системы уравнений, являющиеся индикатором ошибок
в i-м пакете.

Неисправен второй пакет:

S2+h1*S3=0, S1+h2*S3=0 (1.8)

Неисправен третий пакет:

S2+h2*S3=0, S1+h4*S3=0 (1.9)

Неисправен четвертый пакет:

S2+h3*S3=0, S1+h6*S3=0 (1.10)

Неисправен пятый пакет:

S2+h4*S3=0, S1+h8*S3=0 (1.11)

Неисправен шестой пакет:

S2+h5*S3=0, S1+h10*S3=0 (1.12)

Неисправен седьмой пакет:

S2+h6*S3=0, S1+h12*S3=0 (1.13)

Неисправен восьмой пакет:

S2+h7*S3=0, S1+h14*S3=0 (1.14)

Неисправен девятый пакет:

S2+h8*S3=0, S1+h1*S3=0 (1.15)

Неисправен десятый пакет:

S2+h9*S3=0, S1+h3*S3=0 (1.16)

Неисправен одиннадцатый пакет:

S2+h10*S3=0, S1+h5*S3=0 (1.17)

Неисправен двенадцатый пакет:

S2+h11*S3=0, S1+h7*S3=0 (1.18)

Неисправен тринадцатый пакет:

S2+h12*S3=0, S1+h9*S3=0 (1.19)

Неисправен четырнадцатый пакет:

S2+h13*S3=0, S1+h11*S3=0 (1.20)

Неисправен пятнадцатый пакет:

S2+h14*S3=0, S1+h13*S3=0 (1.21)

После определения номера искаженного пакета, для исправления ошибки
необходимо сложить по модулю два данный пакет с синдромом S3i.

При отсутствии ошибки в информационных разрядах необходимо проверить
наличие ошибок в контрольных разрядах. Если существует ошибка в одном из
контрольных разрядов, полученный синдром будет иметь вид:

S3=0, S2=0, S1=e или S3=0, S2=e, S1=0 или S3=e, S2=0, S 1=0 (1.22)

Ошибка в 16-ом пакете:

S14=0. (1.23)

Ошибка в 17-ом пакете:

S41=0. (1.24)

Ошибка в 18-ом пакете:

S24=0 (1.25)

8

D

F

L

? „ – TH

gd©jI

FfD

??????????

??????????

>Ошибка в 17-ом пакете исправляется сложением по модулю два разрядов
пакета и синдрома S2i , в 18-ом пакете- сложением по модулю два разрядов
пакета и синдрома S3i.

На основании рассмотренного выше материала можно сделать следующие
выводы:

1) модифицированный код Рида-Соломона имеет: k=60 информационных
разрядов, r=12 контрольных разрядов, длина кода n=72 ;

2) избыточность кода К= r/n= 0.167;

3) относительная скорость кода R= k/n = 0.83;

4) минимальное расстояние Хемминга dmin = n-k+1=13;

5) код исправляет одноразрядные и обнаруживает двухразрядные пакетные
ошибки;

2 Этапы разработки.

2.1 Функциональный уровень.

Функционирование декодера разделено на три конвейерных уровня. На первом
формируются вектора синдромов ошибки, на втором выполняется определение
номера искаженного пакета принимаемого сообщения (согласно 1.7-1.25), на
третьем – коррекция искаженного пакета. В каждом уровне для сохранения и
передачи данных на следующий уровень использованы регистры.

Кодер имеет один конвейерный уровень, на котором формируются двенадцать
контрольных разрядов.

Для описания функционирования был выбран язык VHDL. Существует две
важные причины для использования VHDL вместо традиционного
схематического проекта – более короткое время разработки электронного
проекта и более простое сопровождение. VHDL позволяет работать с
реальным параллелизмом вместо последовательных машин. VHDL-код
современными пакетами САПР синтезируется в файл для программирования
ПЛИС.

Распараллеливание и конвейеризация описываются в VHDL языке с помощью
процессов, которые запускаются при изменении одного из параметров в
списке чувствительности.

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

2.2. Структурный уровень.

Для синхронизации конвейера все процессы запускаются по тактовому
импульсу. Тактовая частота устройства определяется задержкой
максимального конвейерного уровня.

Для микросхемы Virtex фирмы Xilinx, у которой время сохранения данных в
регистре равно 2 ns, время задержки LUT (LUT-генератор логических
функций, в данном проекте этот блок выполняет сложение по модулю два)
равно 0.7 ns, были получены следующие максимальные расчетные частоты:

–   для кодера 133 МГц;

–   для декодера 99 МГц.

В качестве инструмента синтеза в проекте использована система
проектирования Foundation 3.1 фирмы Xilinx (5). Синтез подобен
компилятору для программного обеспечения.

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

Для синтеза была выбрана ПЛИС FPGA, так как эти ПЛИС наиболее подходят
для конвейерной архитектуры, где в течение одного такта несколько
ступеней или узлов выполняют обработку проходящих данных (3).

Для проведения оптимального синтеза, необходимо корректно задать входные
ограничения. Для этого вначале проведен синтез на самой мощной из
микросхем

V1000 FG 680, а затем, основываясь на результатах выходного протокола,
определена оптимальная микросхема-V50 PG 240. Характеристики ПЛИС V50 PG
240 приведены в таблице 2.1 (4).

Таблица 2.1 – Характеристики ПЛИС FPGA V50 PG 240.

1 Количество логических ячеек 1,728

2 Число системных вентилей 57,906

3 Общее число блоков CLB 384

4 Матрица CLB 16х24

5 Количество входов- выходов 166

6 Количество одноразрядных регистров 1,536

 

Синтез был проведен как с оптимизацией по времени, так и с оптимизацией
по площади. Результаты синтеза приведены в таблице 2.2.

Таблица 2.2 – Результаты синтеза с оптимизацией по площади и времени.

 

Характеристики Кодер Декодер

по времени по площади по времени по площади

Число входов- выходов 133 133 134 134

Одноразрядных регистров 132 132 228 228

Количество слайсов 135 136 352 289

Количество LUTs 107 108 425 309

Максимальная частота,МГц 108.436 105.921 79.485 79.340

 

Анализ результатов синтеза показал, что оптимальный синтез был получен в
результате оптимизации по площади.

В результате синтеза с оптимизацией по площади для декодирующего
устройства при незначительном уменьшении частоты уменьшилось количество
используемых слайсов, что в свою очередь уменьшило степень заполнения
ПЛИС на 12%. Экономия площади дает возможность при необходимости
разместить на данной ПЛИС другое устройство.

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

 

Заключение.

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

Таким образом, кодирование может обеспечить достаточно высокую
достоверность передачи или обработки информации. А такой язык, как VHDL
– входной язык многих современных систем автоматизированного
проектирования (САПР) как заказных, так и программируемых логических
интегральных схем (ПЛИС) и программируемых пользователями вентильных
матриц (FPGA), дает реальную возможность справиться с этой задачей (6).

 

 

 

 

Литература

 

1.             Блейхут .Теория и практика кодов, контролирующих
ошибки.-М.: Мир,1986.

2. Шувалов В.П., Захарченко Н.В., Шварцман В.О. и др. Передача
дискретных сообщений.-М.: Радио и связь,1990.

3. I.Bhasker. A VHDL SYNTHESIS PRIMER. Second edition.1058 Treeline
Drive, Allentown, PA18103.

4. The Programmable logic. Data Book Copyringht 1999,Xilinx,Inc All
Rights Reserved.

5. Peter J. Ashenden. The Designer’s Guide to VHDL. Morgan Kaufmann
Publishers, Inc. San Francisco, California.

6. Бибило П.Н. Основы языка VHDL.-М.:Солон-Р, 2000.

Нашли опечатку? Выделите и нажмите CTRL+Enter

Похожие документы
Обсуждение
    Заказать реферат
    UkrReferat.com. Всі права захищені. 2000-2019