Файл: Хетагуров, Я. А. Повышение надежности цифровых устройств методами избыточного кодирования.pdf

ным элементом и

хх~1=х~'х=1.

Другими

словами, понятие группы

может быть введено с по­

мощью аксиом.

Аксиома

J (замкнутость). Введенная

операция применяется к лю­

элемент

группы.

Аксиома 2 (ассоциативный закон).

Если х,

у,

z & M , то

х+

+iy+z)

= (х+у)

+z

или x(yz) =

(xy)z.

Аксиома

3. Существует нулевой

(единичный)

элемент.

Аксиома

4.

Для

любого

x e A f

существует

такой

элемент

(—х)е=М

(х~1еМ),

что х+(—*)

=

(—х)+х=0.

Группа

обладает

единственным

нулевым

(единичным) элементом.

Если, кроме того, операция, определенная в группе, коммутатив­

на, т. е. для любых

х,

(/е=М х+у=у+х(ху=ух),

то такая

группа

называется

коммутативной или

обелевой.

Группа называется

конечной, если множество ее элементов конеч­

но, и бесконечной — в противном случае. Количество элементов ко­

нечной группы называется порядком

группы.

Примеры.

1. Множество всех «-разрядных

двоичных чисел образует абелеву

группу порядка 2" относительно операции

поразрядного

сложения

чисел по модулю 2. Нулевым элементом

этой

группы

является

число

тивоположным

является сам элемент х, так как

х®х=0.

2. В теории

чисел классом

по данному модулю пг называется

множество всех целых чисел, сравнимых с некоторым данным

целым

числом а. Если обозначить такой

класс знаком [а], то [а] образовано

множеством

всех x = a ( m o d / л ) .

При этом, если

два класса

имеют

хотя бы один

общий элемент, то они совпадают.

Число классов по модулю m конечно и равно т. Например, по

модулю 7 имеем классы: {0}, {1}, {2}, {3}, {4}, {5}, {6}. Вычетом

клас­

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

следующим образом:

суммой

классов

{а} и {6} называется

класс

{а+b},

т. е. содержащий число

а+Ь.

Роль

нулевого

элемента выполняет

класс 0, так как {а}+{0}=

={я]. Дл я класса

{а}

противоположным

является {—а}, т. е. класс,

содержащий число —а.

Подгруппы

Подмножество Я группы М называется подгруппой группы М,

если

в нем удовлетворены аксиомы группы. Всякая

подгруппа

груп­

пы М является группой относительно той операции,

которая опреде­

лена в М.

Пусть Я является подгруппой группы М. Тогда множество

всех

элементов

вида x+h,

получающихся при сложении

элемента

хеМ

с каждым

элементом из Я, называется левым смежным классом

груп­

ные классы обозначаются хН и Их соответственно.

Можно показать, что два любых

смежных класса

либо

совпа­

дают, либо не имеют ни одного общего

элемента.

Одним из левых смежных классов является сама подгруппа Я.

Действительно, если в качестве определяющего выбрать

нулевой

(единичный) элемент группы М, то 0+Н=Н, (1 -Н=Н).

Все осталь­

ные левые смежные классы по подгруппе Н подгруппами

М не явля­

ются.

аддитивно,

а

второй

закон композиции — мультипликативно.

Другими

словами, структура

кольца К удовлетворяет

следующим

аксиомам:

Аксиома

1. Множество К является абелевой

группой

относитель­

но сложения.

Аксиома

2 (замкнутость). Если а, бе/С, то а&е/С.

Аксиома

3 (двойная

дистрибутивность). Для любых элементов

а, Ь, с е Д , a(b+c)=ab+ac

и (b +

c)a—ba+ca.

Операция умножения

в кольце, вообще говоря, не обязана быть

ни ассоциативной, ни коммутативной. В соответствии с этим

говорят

об ассоциативном

кольце

К [если для любых

а, Ь, с^К

справедливо

a(bc)

= (ab).c] и ассоциативно-коммутативном

кольце.

Полем называется ассоциативно-коммутативное кольцо

К, в ко­

тором для любого

элемента а, исключая нулевой

элемент 0, и любого

&е/С

существует

только

один такой элемент

х,

что ах—Ь.

Элемент

х=Ь/а

называется

частным от деления элемента

b на элемент а.

Другими

словами, поле определяем как кольцо /(, множество

ненулевых

элементов

которого

образует коммутативную

(абелеву)

любых элементов а и b мультипликативной

коммутативной группы

записываем а а - 1 = 1, baarl — \b = b, а й а - 1 = 6 ,

ах—Ь.

Приведем

пример поля, которым нам придется

часто пользовать­

ся: множество

из двух элементов (0, 1), в

котором

введена операция

суммирования

по модулю 2 и логического

умножения (выполняемо­

го по правилу:

0-1=-1 - 0=0 - 0 = 0; 1 = 1).

Векторные

пространства и линейная алгебра

Группы, где наряду

с внутренними законами

композиции участ­

именуются

скалярами.

Множество элементов V называется векторным

пространством

над полем Q, если оно удовлетворяет

следующим

аксиомам:

Аксиома

1. Множество V" является

абелевой группой

относитель­

но сложения.

Аксиома

2. Для любого

вектора

v

(элемента

множества

V) и

любого скаляра со (элемента поля Q) определено произведение иш,

которое является

вектором.

Аксиома

3 (дистрибутивный закон). Если

и и

v — векторы,

а с

и d — скаляры, то

c(u+v)

= cu+cv

и

(c+d)v =

cv+dv.

Аксиома

4 (ассоциативный

закон). Если

v — вектор, а

с и

d —

скаляры, то

(cd)v=c(dv)

и

\'V—v.

Более общим понятием, чем векторное пространство,

является

понятие

линейной

алгебры.

Отличие

векторного

пространства

над

полем Q

от

линейной

ассортэтивной

алгебры

над

Q

заключается

в том, что множество

V в первом

случае

является

абелевой

группой,

а во втором — ассоциативным

кольцом.

Рассмотрим совокупность

из п элементов,

которая

обозначается

(oi, аг

а п ) , где си, £ =1, 2, 3, ... , суть

элементы

поля. Для

таких

ляр (элемент поля)

следующим

образом:

(ai, аг,

.... an) +

(bi, bz,

6 n ) = ( a i + 6 i ,

a2+b2, ..., an +

bn)\

c(ait

a2, ...,

an)

= (calt саг

can).

Тогда

множество всех

совокупностей из п элементов,

наделен­

значается

символом 0:

0 = ( 0 , 0, ... . 0).

Для

любого вектора 0i> = u0=0 и для любого скаляра с 0 = 0 с = 0 .

Более

подробные

сведения

можно

найти в

следующих книгах:

1. Мишина

А. П., Проскуряков И. М. Высшая алгебра (линейная

алгебра,

многочлены,

общая

алгебра). М.,

Физматгиз,

1962,

с. 249—281.

2. Курош А. Г. Лекции

по общей алгебре. М., Физматгиз,

1962.

П раложение 2

Таблица степеней двойки

2"

я

2 " п

1

0

1,0

2

1

0,5

4

2

0,25

8

3

0,125

16

4

0,062 5

32

5

0,031

25

64

6

0,015 625

128

7

0,007,812 5

256

8

0,003 906 25

512

9

0,001

953 125

I 024

10

0,000 976 562 5

2 048

11

0,000 488 281 25

4 096

12

0,000 244 140 625

8 192

13

0,000 122 0703125

16 384

14

0,000 061 035 156 25

32 768

15

0,000 030 517 578 125

65 536

16

0,000 015 258 789 062 5

131 072

17

0,000 007 629 394 531 25

262 144

18

0,000 003 814 697 265 625

524 288

19

0,000 001 907 348 6328125

1 048 576

20

0,953 674 316 406 25-10-"

2 097 !52

21

0,476 837 158 203 125-Ю-"

4 194 304

22

0,238418579 101 5 6 2 5 - Ю - 6

8 388 608

23

0,119 209 289 550 781 25 • 10 - 8

16 777 216

24

0,59 604 644 775 390 625-10-'

33 554 432

25

0,29 802 322 387 695 312 5-10-'

67108 864

26

0,14 901 161 193 847 656 25-10-'

134217 728

27

0,07 450 580 596 923 828 1 2 5 - Ю " '

268 435 456

28

0,3 725 290 298 461

9 1 4 0 6 2 5 - Ю - 8

536 870 912

29

0,1 862 645 149 230 957 031

2 5 - Ю " 8

1 073 741 824

30

0,0 931 322 574615 478515 6 2 5 - Ю - 8

2 147 483 648

31

0,0 465 661 287 307 739 257 812 5-10"8

4 294 967 296

32

0.232 830 643 653 869 628 906 25 • 10 - 8

8 589 934 592

33

0,116415321 826 934814453 125-10"»

17 179 869184

34

0,058 207 660 913 467 407 226 562 5 • 10 " 9

34 359 738 368

35

0,029 103 830 456 733 703 613 281 25-10-»

5.

Лапин

В. С. Об одном

методе исправления

групповых

оши­

бок

на

магнитной

ленте.— В

кн.: Цифровая вычислительная техни­

ка

и программирование, вып. 4. М., «Советское

радио»,

1968.

6.

Massey

J.

L.

Error-correcting codes applied

to

computer

technology. Proc.

Natl. .Electronics Conference,

Chicago,

1963.

7.

Базилевич

E. В. и др. Передача

данных.

Информационный

сборник. М., «Связь»,

1969.

8.

Питерсон У. Коды, исправляющие

ошибки. М.,

«Мир»,

1964.

9.

Удалов

А. П.,

Супрун Б. А. Избыточное

кодирование

при

передаче информации

двоичными кодами. М., «Связь»,

1964.