Пороговая схема. 3 страница

Решение. Построим матрицу из 7 строк и 3 столбцов. В -м столбце стоят символы двоичного разложения числа :

.

Так как и 011 – двоичное представление числа 3, то ошибка произошла в третьем разряде. Следовательно, передавалось кодовое слово . Символы с номерами 1, 2, 4 являются контрольными. Поэтому исходное слово - это слово 0111.

Ответ: 0111.

10.1. Составить таблицу вероятностей приёма по двоичному симметричному каналу двухбитовых слов, если вероятность ошибочного приёма одного символа равняется .

10.2. По двоичному симметричному каналу передаются строки длины 14, вероятность ошибочного приёма одного символа равняется .

1) Какова вероятность того, что ровно пять символов будут приняты неправильно?

2) Какова вероятность того, что не более пяти символов будут приняты неправильно?

3) Сколько имеется строк, отличающихся от данной не более чем в пяти позициях?

10.3. Рассмотрим (4,5)-код с проверкой на четность. Какова вероятность того, что не будет обнаружена ошибка при передаче слова длины 9, если вероятность ошибочного приёма одного символа равняется ?

10.4. Рассмотрим (4,5)-код с проверкой на четность и (4,12)-код с тройным повторением. Вычислить вероятность того, что ошибочно переданное слово длины 4 не будет обнаружено, если вероятность правильного приема одного символа равна .

10.5. Доказать, что минимальное расстояние от данного кодового слова до остальных не зависит от выбора данного слова в групповом коде.

10.6. Доказать, что следующие преобразования кодирующей матрицы приводят к эквивалентному коду:

1) перестановка строк;

2) перестановка столбцов;

3) прибавление к одной строке другой.

10.7. Пусть - единичная матрица порядка , - некоторая -матрица. Кодирующая матрица вида называется стандартной. Построить стандартную матрицу, порождающую код, эквивалентный коду с матрицей

.

10.8. Для предыдущего кода построить схему декодирования, используя в качестве лидеров смежных классов слова наименьшего веса. Найти вероятность правильного декодирования, если вероятность ошибки при приёме одного символа равна .

10.9. Рассмотрим двоичный групповой код с матрицей

.

1) Найти стандартную матрицу, дающую эквивалентный код.

2) Построить схему декодирования.

10.10. Для (4,7)-кода Хемминга построить

1) кодирующую матрицу;

2) найти все кодовые слова с контрольными символами 110.

3) переданные слова, если были приняты 0111110, 0001111.

10.11. Построить кодирующую матрицу и проверочную матрицу для:

1) (6,7)-кода с проверкой на четность;

2) (3,9)-кода с тройным повторением.

10.12. Показать, что кодовые слова группового кода либо все имеют четный вес, либо половина четный, а половина – нечетный.

10.13. Показать, что -код, , с тройным повторением не может быть совершенным.

10.14. Рассмотрим (3,6)-код с обнаружением ошибок, имеющий матрицу

.

Найдите вероятность того, что ошибка в передаче слова длины 6 не будет обнаружена, если вероятность ошибки при приёме одного символа равна .

ОТВЕТЫ

1.1. 1) , 2) , 3) , 4) ,

5) .

1.3. 1087, 2011.

1.12 1) 501, 2) 333.

1.13. 1) , 2) ,

3) , 4) ,

5) 6=1 78 6 60+12 24.

1.14. 1) 70151, 2) 166608, 3) 17081, 4) 23607, 5) 1560.

1.16. 13.

1.21. не существует.

1.22. ( - простое число).

1.23. 1.

2.1. 1) , 2) , 3) ,

4) .

2.2. 1) , 2) ,

3) , 4) решений нет,

5) ().

2.3. 1) , , 2) x =25+30 s +70 r +8 t, y =–15–18 s –42 r –5 t, , 3) ,

4) , , ().

2.5. 1) , 2) , 3) ,

4) , 5) , 6) ,

7) , 8) решений нет, 9) .

2.6. 1) z =8 r – t, ,

2) , 3) , , 4) , .

2.7. , или , , где , , , .

2.13. решений нет.

3.1. 1) 18, 2) 110, 3) 96, 4) 240, 5) 1152.

3.2. 88.

3.3.

3.5. 1) 5, 2) 7.

3.7. 1) 12, 2) 27, 3) 44, 4) 12.

3.8. 1) 46, 2) 7, 3) 1067, 4) 50, 5) 136.

3.9. 1) 19, 2) 215, 3) 225, 4) 118, 5) 445.

3.10. 1) 399, 2) 1811, 3) 479, 4) 317.

3.12. , .

3.16. 1) , 2) решений нет.

3.15. 3.

4.1. 1) 28, 2) 0, 3) 528, 4) 20, 5) 6.

4.2. 1) ,

2) , 3) ,

4) , 5) .

4.3. 1) 10, 2) 7, 3) 5, 4) 9, 5) 11.

4.4. 1) , 2) ,

3) , 4) ,

5) .

4.5. 1) да, 2) нет, 3) нет, 4) нет, 5) да.

4.6. 5.

4.9. ; ; ;

.

4.11. 1.

4.12. .

4.13. .

4.14. 7, 37.

4.15. 1) , 2) , 3) , 4) , 5) .

5.1. 1) , 2) , 3) ,

4) , 5) решений нет.

5.2. 1) 2) , 3) ,

4) , 5) .

5.3. 1) , 2) , 3) , 4) решений нет, 5) .

5.5 1) , 2) , 3) ,

4) , 5) .

5.6. 1) , 2) ,

3) , 4) ,

5) .

5.7. 1) ; , 2) , , , 3) , , .

5.8. при ; при ; при ; при , где - число простых делителей числа .

5.10.

5.11. 1), 3) разрешимы; 2),4),5) нет решений.

6.1. 1) ни одно из множеств не образует группу; 2) группы: , , , ; 3) не группа; 4) группы: , , ; 5) группы: , ; 6) группа для любого ; 7) группа; 8) группа; 9) группа; 10) группа; 11) группа при ; 12) группа; 13) не группа; 14) группа для любого ; 15) группы; 16) группа для любых ; 17) группа при ; 18) группа для любого ; 19) группа; 20) группа при .

6.2. 1) не являются; 2) являются; 3) не являются; 4) являются;

5) являются; 6) являются.

6.3. .

6.4. , .

6.5. 1) ; 2) , , ;

3) , где , .

6.6. 1) , , , ,

, ; 2) , ,

, , , ,

где ; 3) , где . Все подгруппы нормальные.

6.11. 1) 2; 2) 6; 3) 20.

6.12. 1) 6; 2) 8; 3) 4; 4) 2.

6.13. 1) ; 2) ; 3) .

6.14. .

6.15. .

6.19. ; , ,

, .

6.20. 1) 3; 2) 3; 3) 12.

6.21. 1) ; 2) .

7.1. 1) кольца: ; 2) кольцо; 3) кольцо для любого ;

4) кольцо; 5) кольцо; 6) не кольцо; 7) кольцо; 8) кольцо; 9) кольцо;

10) не кольцо; 11) кольцо.

7.2. 1) , ; 2) ;

3) ;

4) Z ₂₀₁₀, 2 Z ₂₀₁₀, 3 Z ₂₀₁₀, 5 Z ₂₀₁₀, 6 Z ₂₀₁₀, 10 Z ₂₀₁₀, 15 Z ₂₀₁₀, 30 Z ₂₀₁₀,

67 Z ₂₀₁₀, 134 Z ₂₀₁₀, 201 Z ₂₀₁₀, 335 Z ₂₀₁₀, 402 Z ₂₀₁₀, 670 Z ₂₀₁₀, 1005 Z ₂₀₁₀, 2010 Z ₂₀₁₀.

7.3.

1) ; 2) ; 3) ; 4) .

7.4. 1) вещественные верхние треугольные матрицы с ненулевыми элементы на диагонали; 2) ; 3) .