Методическое пособие для выполнения РГЗ - Разработка системы кодирования-декодирования циклического кода (1267327)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Министерство образования и науки РФНовосибирский Государственный Технический УниверситетМЕТОДИЧЕСКОЕ ПОСОБИЕ ДЛЯ ВЫПОЛНЕНИЯРАСЧЁТНО-ГРАФИЧЕСКОГО ЗАДАНИЯПо курсу: «Основыпередачи дискретных сообщений».«Разработка системы кодирования/декодированияциклического кода».Новосибирск2006Содержание1. Задание2. Этапы выполнения работы3. Исходные данные4.

Методические указания5. Определение числа проверочных элементов6. Выбор образующего полинома7. Расчёт матрицы синдромов для однократной ошибки8. Изображение схемы устройства кодирования9. Изображение схемы устройства декодирования10. Оценка вероятности необнаруживаемой ошибки на выходе системыпередачи11. Список литературыстр.3стр.3стр.3стр.3стр.4стр.4стр.22стр.22стр.23стр.24стр.252Задание.

Разработать систему кодирования/декодирования циклического кода дляn -элементного первичного кода, который обнаруживает t 0 и исправляет t и ошибок.Оценить вероятность получения необнаруживаемой ошибки на выходе системы, если Pошв канале связи меняется от 10 6 до 10 2 .1.2.3.4.5.Этапы выполнения работы:Определение числа проверочных элементов.Выбор образующего полинома.Расчёт матрицы синдромов для однократной ошибки.Изображение схем устройств кодирования, декодирования.Построение графика появления необнаруживаемой ошибкивероятности ошибки в канале связи.приизмененииИсходные данные.

Необходимые для решения задачи исходные данныевыбираются по таблице 1 в соответствии с полученным вариантом.Таблица 1Исходные данные для вариантов расчетно-графической работы.Вариант №Количествоэлементов вкоде kКоличествоисправляемыхошибок t иВариант №Количествоэлементов вкоде kКоличествоисправляемыхошибок t и12345678910111213141516171819205678910567891056789105615324124613233542342212223242526272829303132333435363738394078956786755676981055843151256135246342453Методические указания.

Прежде чем приступить к выполнению задания, изучитепо источникам: [1]-циклические коды, [2]-коды исправляющие ошибки.Расчётно-графическое задание должно содержать следующие разделы: исходныеданные, этапы выполнения работы, вычисления, заключение.3Определение числа проверочных элементов. Исходя из заданных k и t инеобходимо решить систему уравнений:tиk  r ! r  log 2 1   i 1 i!k  r  i ! n  k  rТаким образом, число проверочных элементов в коде равно r , а всего элементов в кодеравно n .Выбор образующего полинома. После определения проверочных разрядов r ,выбирается образующий полином G(x) (многочлен) степени, равной r .Образующий полином G(x) должен обладать некоторыми свойствами:1) Остатки от деления должны быть все разные, т.е.

его нельзя составить из степенейнизших порядков, он неприводимый.2) Число остатков у этого полинома должно быть равно количеству ошибок в коде,т.е. такие полиномы примитивные.В этом пункте даются таблицы, с помощью которых можно найти всенеприводимые многочлены степени 16 или меньше. В таблицах указаны некоторыесвойства этих многочленов и соотношения между ними. Приводятся примитивныемногочлены с минимальным числом ненулевых коэффициентов и многочлены,принадлежащие всем возможным показателям для каждой степени от 17 до 34.Многочлены даны в восьмеричном представлении. Каждый символ в таблицеобозначает три двоичных знака в соответствии со следующим кодом:0 000 2 010 4 100 6 1101 001 3 011 5 101 7 111Коэффициенты многочленов в двоичной записи расположены в порядке убывания,так что коэффициент при слагаемом высшего порядка расположен слева.

Например,3525 обозначает многочлен 10-й степени. В двоичной записи числу 3525 эквивалентночисло 0 1 1 1 0 1 0 1 0 1 0 1, и соответствующий многочлен равен:G( X )  X 10  X 9  X 8  X 6  X 4  X 2  1 .Двойственный многочлен неприводимого многочлена также неприводим, адвойственный многочлен примитивного многочлена примитивен. Поэтому каждый разв таблице приводится либо сам многочлен, либо двойственный многочлен.

Каждаязапись в таблице, оканчивающаяся некоторой буквой, соответствует некоторому неразложимому многочлену указанной степени. Для степеней от 2 до 16 этими многочленами,а также двойственными к ним исчерпываются все неразложимые многочлены этихстепеней.Буквы, которые приведены после восьмеричного представления многочлена, даюто нем следующую информацию:A, B, С, D Не примитивныйЕ, F, G, Н ПримитивныйA, B, Е, F Корни линейно зависимыС, D, G, Н Корни линейно независимыA, C, Е, G Корни двойственного многочлена линейно зависимыB, D, F, Н Корни двойственного многочлена линейно независимы456789101112131415161718192021После выбора полинома, необходимо произвести проверку и определить, подходитли данный полином как образующий. Для этого:1.

Определить кодовое расстояние по формуле: d 0  2  tи  1 .2. Т.к. из условия известно k , то для простоты комбинация первичного кодабудет иметь вид f ( x)  x k 1  100...000 .3. Определить f ( x)  x r  x ( k 1)r (иными словами сместить информационныеэлементы на r - разрядов влево).4. Разделить f ( x)  x r на G(x) , полученный остаток от деления r (x) комбинация проверочных элементов.5.

Записать многочлен комбинации F ( x)  f ( x)  x r  r ( x) и определить весV (количество единиц в комбинации).6. Сравнить V с d 0 , в случае если V  d 0 , то выбранный полином подходит какобразующий.Расчёт матрицы синдромов для однократной ошибки. Для определенияэлементов матрицы синдромов, необходимо вносить ошибку в кодовую комбинациюF (x) поочерёдно, начиная со старшего разряда, затем делить на образующий полиномG(x) , полученный остаток ai или bi и будет одной из строк матрицы синдромов, котораяимеет вид:00...000r ( x)  a1a2a3S.....akb1b2.....brвсе _ верныошибка _ в _ разряде _ а1ошибка _ в _ разряде _ а2ошибка _ в _ разряде _ а3....., г деошибка _ в _ разряде _ аkошибка _ в _ разряде _ b1ошибка _ в _ разряде _ b2.....ошибка _ в _ разряде _ brСхема кодера циклического кода (n,k).

Необходимо устройство, котороевычисляет:f ( x)  x r.G ( x)В общем виде образующий полином G(x) можно представить в виде:G( x)  g k 1 x k 1  g k 2 x k 2  ...  g 2 x 2  g1 x  g 0 .Для вычисления такого выражения необходимо устройство, которое представляет собойсдвиговый регистр с обратными связями, число ячеек которого равно степениобразующего полинома, а положение сумматоров определяется не нулевымикоэффициентами полинома (рис.1):22Рисунок 1.Схема кодера циклического кода.Принцип работы устройства:В исходном состоянии ключ находится в положении 1, на вход устройствапоступает первичная кодовая комбинация f(x) (начиная со старшего разряда).

Через kтактов вся первичная кодовая комбинация поступит на выход, а в результате деления(благодаря обратной связи) образуется остаток. Ключ переключается в положение 2.Таким образом, через n-тактов на выходе получим F(x).Схема декодера циклического кода (n,k).Рисунок 2.Схема декодера циклического кода.23Принцип работы устройства:Исходная комбинация F(x) подаётся в буферный регистр и одновременно вдекодирующий регистр. Если с приходом последнего символа, зафиксирован нулевойостаток (синдром 000…00), то ошибок нет, если же не нулевой, то есть.

Принятаякомбинация подаётся через выходной сумматор, и искажённый сигнал исправляется.Оценка вероятности необнаруживаемой ошибки на выходе системы передачи.Все ошибки в коде – независимы, т.е. распределение у такого кода биноминальное.Вероятность появления i – ошибки в n – элементной комбинации:iP(i, n)  Cni  Pош (1  Pош ) ni , 0  i  nNгде Pош  lim ош , N ош - ошибочные комбинации, N - все комбинации.NN 1Для регулярного канала связи, Pош примерно одинакова.

Вероятность правильного приёма:P(0, n)  (1  Pош ) n .Вероятность появления хотя бы одной ошибки:P( 1, n)  1  (1  Pош ) n .Если n  Pош  1 , то обычно вероятность появления хотя бы 1-ой ошибки считают:P( 1, n)  n  Pош .Вероятность появления i и более ошибок:nni 1i 1iP( i, n)   P(i, n)  Cni  Pош(1  Pош ) n1Необнаруживаемая ошибка – это когда в результате ошибки одна разрешённаякомбинация заменяется на другую разрешённую комбинацию.Вероятность ошибки в канале связи Pош меняется от 10 6 до 10 2 . Таким образом,зависимость вероятности необнаруживаемой ошибки от ошибки в канале связи имеет вид:PНО ( Рош ) 12 nkni tи 1n!in 1 )(1P)ошош  i!n  i !  ( PПостроить график.

Объяснить полученную зависимость.24Список использованной литературы.1. Питерсон У., Уэлдон Э. Коды исправляющие ошибки. М.: Мир, 1976г.2. Мак-Вильямс Ф.Дж., Слоэн Н.Дж. Теория кодов, исправляющих ошибки. М.:Радио и связь, 1979г.25.

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов книги