Экстремальные коды
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
трицы Адамара.
Матрицей Адамара называется ортогональная (KK) - матрица, элементами которой являются числа +1 и - 1. Например:
H2 = =
H4 =
Без потери общности можно предположить, что все элементы первой строки и первого столбца матрицы Адамара равны +1. Отбрасывая первый столбец (KK) - матрицы Адамара, получим K строк длины K-1, образующих двоичный эквидистантный код. Если K не есть степень числа 2, то получается нелинейный код.
Теорема 3. (Нижняя граница Варшамова - Гилберта).
(n, k) - код (линейный) с минимальным кодовым расстоянием d, параметры которого удовлетворяют неравенству:
.
-
вероятность получить не более (d-2) успехов в схеме Бернулли.
Граница Варшамова - Гильберта является границей существования и дает нижнюю оценку кодового расстояния для "наилучшего" кода.
Теорема 4. (Оценка Чернова для биномиальных коэффициентов).
Пусть , то справедливо:
Из этих неравенств следует:
) , d = 2t + 1
) - следует из гр. Плоткина в случае лин. кода
) - из гр. Варшамова-Гилберта
Заключение
Применение кодов
Первым кодом, исправляющим ошибки, который стал применяться в вычислительных машинах, был разработанный еще на заре теории кодирования в 1950 г. код Хэмминга. Этот код был разработан специально для применения в вычислительных машинах. Код Хэмминга стал применяться в вычислительных машинах не сразу, и это объясняется тем, что после появления кода Хэмминга постоянно совершенствовались сами запоминающие элементы; сначала использовались электронные лампы, далее появились параметроны, полупроводниковые элементы и наконец интегральные схемы. При этом надежность запоминающих элементов постоянно и быстро росла. Первой вычислительной машиной, в которой использовался код Хэмминга, была вычислительная машина IBM 7030, а в Японии - машина DIPS фирмы Japan Telephone and Telegraph Public. Однако если первая была построена спустя 10 лет после появления кода Хэмминга, то вторая - спустя 20 лет. До этого времени в вычислительных машинах использовался лишь простейший способ повышения надежности, а именно проверка на четность (или нечетность)
Код кратных повторений, который является эквидистантным кодом, предназначен для кодирования двоичной информации. Он обладает большой помехозащищенностью, но очень малой скоростью передачи информации.
В последние годы различные достаточно сложные коды, исправляющие большое число ошибок, начали применяться как в самих вычислительных машинах, так и в периферийном оборудовании, в частности в накопителях на магнитной ленте. По мере развития вычислительной техники коды, исправляющие ошибки, будут играть всё большую роль в повышении надежности вычислительных систем.
Технология применения кодов в современных условиях преследует цели защиты информации, сокращения трудозатрат и обеспечение быстроты ее обработки, экономии компьютерной памяти, формализованного описания данных на основе их систематизации и классификации.
экстремальный код равенство параметр
Список используемой литературы
1. А. А. Духин "Теория информации", Москва, Гелиос АРВ, 2007 г.
. Касами Т. "Теория кодирования" издательство "мир", Москва, 1978 г.
. Н.В. Семаков, В.А. Зиновьев "Эквидистантные q-ичные коды с максимальным расстоянием и разрешимые уравновешенные блок-схемы" (1967 г.)