Конечные поля. Том 1 - Лидл Р.
ISBN 5-03-000065-8
Скачать (прямая ссылка):
информации передается по каналу не изменяясь. Ввиду того что не
существует идеального канала без "шумов", получатель передаваемого
сообщения может получить искаженную информацию и 0 н 5 и боч но и стол ко
вать п ер еда н н ые с и гнал ы.
Одной нз основных задач теории кодирования является стрем леппе к тому,
чтобы вероятность ошибок, появляющихся в результате шума в канале связи,
была сведена к минимуму. Методы повышения надежности передачи сообщений в
основном базируются на свойствах конечных полей.
Основной идеей алгебраической теории кодирования является передача
избыточной информации вместе с тем сообщением, которое необходимо
передать. Это означает, что последовательность символов, составляющая
передаваемое сообщение, некого-Рым специальным образом преобразуется в
более длинную после-
Аовател ьноеть
' 1 * * с-" а.*" л
Гл. 9. Приложения конечных полей
ЫЫМЫ^ьЛМт О • | | 1*1* Y Д
-.1 • Щ.1 1*М I - ¦ I I Г*| П ~ ~ II1111I1I 'г'К'-1'т1Т 1 |~ ¦ 1111 'и
Ь'Г| | у -| I1 УГ II ¦ 11' I • I Ill ¦ УЙ I 11 ' I I II '¦
|'|~|' |~| |'|
Простая модель системы связи изображена на рис. 9,1
ЫРЛЧ-Л%|
й
ь-
f
№
^---
• * * * SVhWJ Ы ь
< aiai4 Т • *ф"ф"ф"Л ¦ * ¦ а" .
ДгКН.ИзрО]Д*!Ш<Х
а
g
Пояучс-шюе
гхкюищдже
Кл/ШХ TriHJH
€
Ш
€ *е
Рис. 9Л
предполагаем, что символы, составляющие исходное со обще и символы,
составляющие закодированное сообщение, явля элементами одного н того же
конечного поля Fg. Кодирован1 означает, что блок нз к символов
передаваемого сообщен
а, До
а
о.} ? F,,, заменяется кодовым словом сум ,с.
u I С Li "">С1МС11Л*; i ^ гдноищ Ь]1'2 ' < ¦ 4.- -fl ДЛ|$:
п > k, которое образовано символами щ б Fy. Мы будем pi;
сматривать кодовое слово как я-мерпую вектор-строку с ? Таким образом,
отображение / на рис. 9.1 является функця$
из F'J в F% называемой схемой кодирования, a g функцз
п в fj, называемой схем ой декодирования.
из
я
Простая разновидность схемы кодирования возникает в с, чае, когда в
сообщении каждый блок нз k символов аха., ... кодируется кодовым словом
вида
ПУЩ ' ¦ ¦> ^9ХЛ+1 ' ' ' По
где первые ? символов совпадают с к символами исходного сЩ| щення и
называются информационными символами, а дополЦ тельные я - к символов щ б
§q называются проверочными (щ контрольными) символам и. Такую схему
кодирования часто прй| ста вл я ют в следующем виде. Пусть // заданная (п
- k) X.J
Дф Ф Ф "S
матрица, образован пая элементами ноли F^ н имеющая вид
Щ
Н - (Л <"
ч.Зю
где Л -- матрица размера (а - k) х k, а единичН
матрица порядка п - k. Тогда проверочные символы сь+,. ... могут быть
определены из системы уравнений
Ясг - О,
. л
т
где е - кодовое слово, а 1 обозначает транспонирование, нении, образующие
эту систему, называются проверочными нениями или уравнениями проверки на
четность 1}"
¦^1*ф^гф"Ч I I Р"Я
1) Название берет свое начало в исследованиях по бинарным кодам* тН кодам
над полем JX - Прим,
§ 1. Линейные коды 589
: : I,-*^ j -----------------------------------у, т, , | , г i
П----* '*n t * ''i i"i * .........-Л LM*IM H M
- ь"ч ,¦ . .-¦'-m-t....... ь^ь-." "л*д
bTTT^.Wi^S^-Q
1 ."? H
Пусть Я есть 3 X 7* матрица над полем р., еле-
V i v-p
aviomero вида:
1110 O'
Я f 1 10 10 10
v i i i о о о i
\ vf
Проверочные символы можно найти из системы уравнений //ст fi считая сь
с.у, щ. С| заданными:
Н. ! " is '¦ г" Q г Сг3
С\ *4" '"i И !" (tm) 0.
Н "Г ?;2 3"' 63 С7 ~ 0
Тогда проверочные символы Щ, Ч,, со можно выразить следующш
образом:
•+
> - •• ?
съ Cl. ¦¦ Су г- C|,
Се Ci ........ Ci , ' ( 1 >
С? f* LS b ^ ^ -f~ сг ¦ Су,
значит, схема кодирования в этом случае является линейным отображением из
f\ в F3 которое имеет вид
Ci, си, сд, -¦*-
filj , it-2* Cj, ОД- О] ОТ t/.j, О j {Ы ¦ j" i/,.j, fp (1 •<
\ ?"?§). f_ ]
В общем, случае в связи со схемами кодирования, задаваемыми
линейными отображениями, мы будем пользоваться следующей
терминологией.
0,2, Определение. Пусть И - матрица над полем (р9 размера (л к) х п н
ранга а ¦- к. Множество С всех л-мерных векторов
с t f J. таких, что Яс -...... 0. называется линейным (я, к)-кодом
над нолем fq. Число я называется длиной кода, а к - размерностью кода,
Элементы множества С называются кодовыми сло~ шчн (или кодовыми
векторами). матрица Я называется проверен-
ной матрицей кода С. Если ц 2, С называется бинарным кодом,
Если матрица Н имеет вид Я (А ¦ то код С называется систематическим
кодом,,
Заметим,, что множество С решений системы линейных урав-¦ "ий //ст =¦ 0
является fe-мерным подпространством векторного
пространства f'J. Так как кодовые слова образуют группу по уложению, то С
также называется групповым кодом, Кроме того,
• J 1*Г
iAr " '*
к по рассматривать как нуль-пространство матрицы Я ])
} То есть как ядро линейного отображения? задаваемого матрицей //" или ?
J Tfс Т-Р а нетво решен и й од н ородно н с истем ы л инейных у р л в н с
к и й е м в три -
¦dm i
I ¦ Прим, пере$>
XU
9. Приложений конечных нолей
