Xreferat.com » Рефераты по информатике и программированию » Лекции по количественной оценке информации

Лекции по количественной оценке информации

height="24" />, то число контрольных разрядов Лекции по количественной оценке информации находим из выражения

Лекции по количественной оценке информации

Общее число символов кода

Лекции по количественной оценке информации

Если задана длина кода Лекции по количественной оценке информации, то число контрольных разрядов

Лекции по количественной оценке информации

Соотношение числа контрольных и информационных символов для кодов с  приведены в табл. 3 приложения 9.

2. Выбор образующего многочлена производится по таблицам неприводимых двоичных многочленов.

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

3. Выбор параметров единичной транспонированной матрицы происходит из условия, что число столбцов (строк) матрицы определяется числом информационных разрядов, т. е. ранг единичной матрицы равен .

4. Определение элементов дополнительной матрицы производится по остаткам от деления последней строки транспонированной матрицы (единицы с нулями) на образующий многочлен. Полученные остатки должны удовлетворять следующим требованиям:

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

б) число остатков должно быть не меньше числа строк единичной транспонированной матрицы, т. е. должно быть равно числу информационных разрядов Лекции по количественной оценке информации;

в) число единиц каждого остатка, т. е. его вес, должно быть не менее величины , где Лекции по количественной оценке информации - минимальное кодовое расстояние, не меньшее числа обнаруживаемых ошибок;

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

5. Образующая матрица составляется дописыванием элементов дополнительной матрицы справа от единичной транспонированной матрицы либо умножением элементов единичной матрицы на образующий многочлен.

6. Комбинациями искомого кода являются строки образующей матрицы и все возможные суммы по модулю 2 различных сочетаний строк образующей матрицы.

7. Обнаружение и исправление ошибок производится по остаткам от деления принятой комбинации  на образующий многочлен Лекции по количественной оценке информации. Если принятая комбинация делится на образующий многочлен без остатка, то код принят безошибочно. Остаток от деления свидетельствует о наличии ошибки, но не указывает, какой именно. Для того чтобы найти ошибочный разряд и исправить его в циклических кодах, осуществляют следующие операции:

а) принятую комбинацию делят на образующий многочлен и

б) подсчитывают количество единиц в остатке (вес остатка).

Если Лекции по количественной оценке информации, где s - допустимое число исправляемых данным кодом ошибок, то принятую комбинацию складывают по модулю 2 с полученным остатком. Сумма даст исправленную комбинацию. Если , то

в) производят циклический сдвиг принятой комбинации  влево на один разряд. Комбинацию, полученную в результате циклического сдвига, делят на . Если в результате этого повторного деления  то делимое суммируют с остатком, затем

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

д) повторяют операцию пункта в) до тех пор, пока не будет . В этом случае комбинацию, полученную в результате последнего циклического сдвига, суммируют с остатком от деления этой комбинации на образующий многочлен, а затем

е) производят циклический сдвиг вправо ровно на столько разрядов, на сколько была сдвинута суммируемая с последним остатком комбинация относительно принятой комбинации. В результате получим исправленную комбинацию[18].

II. Коды, обнаруживающие трехкратные ошибки, Лекции по количественной оценке информации.

1. Выбор числа корректирующих разрядов производится из соотношения

Лекции по количественной оценке информации

или

Лекции по количественной оценке информации

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

Лекции по количественной оценке информации

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

3. Построение образующей матрицы производят либо нахождением остатков от деления единицы с нулями на образующий многочлен, либо умножением строк единичной матрицы на образующий многочлен.

4. Остальные комбинации корректирующего кода находят суммированием по модулю 2 всевозможных сочетаний строк образующей матрицы.

5. Обнаружение ошибок производится по остаткам от деления принятой комбинации  на образующий многочлен Лекции по количественной оценке информации. Если остатка нет, то контрольные разряды отбрасываются и информационная часть кода используется по назначению. Если в результате деления получается остаток, то комбинация бракуется. Заметим, что такие коды могут обнаруживать 75% любого количества ошибок, так как кроме двойной ошибки обнаруживаются все нечетные ошибки, но гарантированное количество ошибок, которое код никогда не пропустит, равно 3.

Пример: Исходная кодовая комбинация - 0101111000, принятая - 0001011001 (т. е. произошел тройной сбой). Показать процесс обнаружения ошибки, если известно, что комбинации кода были образованы при помощи многочлена 101111.

Решение:

Лекции по количественной оценке информации

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

III. Циклические коды, исправляющие две и большее количество ошибок,

Методика построения циклических кодов с Лекции по количественной оценке информации отличается от методики построения циклических кодов с Лекции по количественной оценке информации только в выборе образующего многочлена. В литературе эти коды известны как коды БЧХ (первые буквы фамилий Боуз, Чоудхури, Хоквинхем - авторов методики построения циклических кодов с ).

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

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

Лекции по количественной оценке информации                                                                    (79)

при этом п всегда будет нечетным числом. Величина h определяет выбор числа контрольных символов Лекции по количественной оценке информации и связана с  и s следующим соотношением:

Лекции по количественной оценке информации                                                    (80)

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

Лекции по количественной оценке информации                                                                 (81)

где Лекции по количественной оценке информации является одним из сомножителей, на которые разлагается число п.

Соотношения между Лекции по количественной оценке информации, С и h могут быть сведены в следующую таблицу

№ п/п h Лекции по количественной оценке информации C
1 2 3 4 5 6 7 8 9 10 3 4 5 6 7 8 9 10 11 12 7 15 31 63 127 255 511 1023 2047 4095 1 5; 3 1 7; 3; 3 1 17; 5; 3 7; 3; 7 31; 11; 3 89; 23 3; 3; 5; 7; 13
Например, при h = 10 длина кодовой комбинации может быть равна и 1023  и 341 (С = 3), и 33 (С =31), и 31 (С = 33), понятно, что п не может быть меньше  Величина С влияет на выбор порядковых номеров минимальных многочленов, так как индексы первоначально выбранных многочленов умножаются на С.

Построение образующего многочлена Лекции по количественной оценке информации производится при помощи так называемых минимальных многочленов Лекции по количественной оценке информации, которые являются простыми неприводимыми многочленами (см. табл. 2, приложение 9). Образующий многочлен представляет собой произведение нечетных минимальных многочленов и является их наименьшим общим кратным (НОК). Максимальный порядок Лекции по количественной оценке информации определяет номер последнего из выбираемых табличных минимальных многочленов

Лекции по количественной оценке информации                                                                           (82)

Порядок многочлена используется при определении числа сомножителей . Например, если s = 6, то . Так как для построения Лекции по количественной оценке информации используются только нечетные многочлены, то ими будут: Лекции по количественной оценке информации старший из них имеет порядок . Как видим, число сомножителей Лекции по количественной оценке информации равно 6, т. е. числу исправляемых ошибок. Таким образом, число минимальных многочленов, участвующих в построении образующего многочлена,

Лекции по количественной оценке информации                                                                      (83)

а старшая степень

Лекции по количественной оценке информации                                                                      (84)

(Лекции по количественной оценке информации указывает колонку в таблице минимальных многочленов, из которой обычно выбирается многочлен для построения ).

Степень образующего многочлена, полученного в результате перемножения выбранных минимальных многочленов,

Лекции по количественной оценке информации                                                          (85)

В общем виде

Лекции по количественной оценке информации                                      (86)

Декодирование кодов БЧХ производится по той же методике, что и декодирование циклических кодов с Лекции по количественной оценке информации. Однако в связи с тем, что практически все коды БЧХ представлены комбинациями с , могут возникнуть весьма сложные варианты, когда для обнаружения и исправления ошибок необходимо производить большое число циклических сдвигов. В этом случае для облегчения можно комбинацию, полученную после -кратного сдвига и суммирования с остатком, сдвигать не вправо, а влево на  циклических сдвигов. Это целесообразно делать только при .


ТЕМА 8. СЖАТИЕ ИНФОРМАЦИИ

Сжатие информации представляет собой операцию, в результате которой данному коду или сообщению ставится в соответствие более короткий код или сообщение[19].

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

Сжатие информации делением кода на части, меньшие некоторой наперед заданной величины А, заключается в том, что исходный код делится на части, меньшие А, после чего полученные части кода складываются между собой либо по правилам .двоичной арифметики, либо по модулю 2. Например, исходный код 101011010110; A = 4

Лекции по количественной оценке информации  

Сжатие информации с побуквенным сдвигом в каждом разряде [5], как и предыдущий способ, не предусматривает восстановления сжимаемых кодов, а применяется лишь для сокращения адреса либо самого кода сжимаемого слова в памяти ЭВМ.

Предположим, исходное слово «газета» кодируется кодом, в котором длина кодовой комбинации буквы l = 8:

Г - 01000111; а - 11110000; з - 01100011; е - 00010111; т - 11011000.

Полный код слова «Газета»

010001111111000001100011000101111101100011110000.

Сжатие осуществляется сложением по модулю 2 двоичных кодов букв сжимаемого слова с побуквенным сдвигом в каждом разряде.

Лекции по количественной оценке информации

Лекции по количественной оценке информации

Допустимое количество разрядов сжатого кода является вполне определенной величиной, зависящей от способа кодирования и от емкости ЗУ. Количество адресов, а соответственно максимальное количество слов в выделенном участке памяти машины определяется из следующего соотношения

Лекции по количественной оценке информации                                                                       (88)

где Лекции по количественной оценке информации - максимально допустимая длина (количество двоичных разрядов) сжатого кода; N -  возможное количество адресов в ЗУ. Если представить процесс побуквенного сдвига в общем виде, как показано на рис. 1, а, то длина сжатого кода

Лекции по количественной оценке информации

где

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: