Решение.

1) 1100011 2) 1100011

10011111010101

0101100 d₀=W=3 0110110 d₀=W=4

3) 1001111 4) 1001111

10101011100011

0011010 d₀=W=3 0101100 d₀=W=3

Таким образом, d_мин= 3.

Задача 6.45.Определить корректирующие способности следующего кода: 001; 010; 111.

Задача 6.46. Способен ли код исправлять ошибки, если его комбинации имеют вид: 1001010; 0101110; 1101001; 0011011; 1011100?

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

Задача 6.48. Построить матрицу для группового кода, способного исправлять одиночную ошибку при передаче 16 символов первичного алфавита.

Решение. Так как число информационных разрядов кода , то число строк образующей матрицы С должно быть равно 4.

Число столбцов матрицы С равно длине кода n:

где n_И– число корректирующих разрядов. Для кодов с d₀ = 3 (d₀= 2r + 1 = 3)

Тогда

Поскольку для исправления одиночной ошибки d₀ = 3, то число столбцов, содержащих контрольные разряды, равно 3.

Учитывая то, что вес каждой строки проверочной матрицы П должен быть

в качестве строк проверочной матрицы можно взять трехзначные двоичные комбинации с числом единиц, большим или равным 2 (d₀ = 3), а W_П= 1, потому что матрицу информационных разрядов лучше брать единичную: 111; 110; 101; 011.

Окончательный вид производящей матрицы таков:

, или , или , и т.д.

Задача 6.49. Источник передает сообщения при помощи 15 двоичных комбинаций. Составить информационную и проверочную матрицы таким образом, чтобы полная производящая матрица могла производить групповой код, корректирующий одиночные сбои.

Задача 6.50. Построить образующую матрицу группового кода с расстоянием между кодами d₀ = 3, способного передавать 100 различных сообщений и обладающего потенциальной способностью коррекции возможно большего числа ошибок.

Решение.Для передачи 100 сообщений необходимо соблюдение неравенства , откуда n_И= 7. При n_И = 7 и d₀ = 3

Таким образом, число строк образующей матрицы n_И = 7, число столбцов равно . Поскольку число корректирующих разрядов равно 4 и порождаемый код должен исправлять возможно большее число ошибок, то в качестве строк проверочной матрицы П последовательно выписываем четырехзначные двоичные комбинации весом W_П = 4, 3, 2 (1111, 1110, 1101, 1011, 0111, 1100, 1010, 1001, 0110, 0101, 0011) и используем из них те комбинации, в которых большее число единиц.

Так как n_И = 7, выбираем 7 комбинаций. Проверочную матрицу следует строить таким образом, чтобы число единиц в колонках матрицы П было по возможности одинаковым, так как от числа единиц в колонке матрицы П зависит число проверок, производимых при исправлении ошибок (см. задачу 6.65).

Матрица плотно упакованного кода (11; 7) имеет вид:

Задача 6.51. Построить производящую матрицу группового линейного кода, исправляющего максимально возможное число вариантов ошибок кратностью r + 1, r + 2 и т. д. при передаче пятнадцатиразрядных двоичных информационных комбинаций.

Задача 6.52. Какой вид имеет порождающая матрица группового кода, оптимального с точки зрения минимума корректирующих разрядов при максимуме информационных разрядов, для использования его в системе телемеханики, проектируемой для передачи не менее 2000 различных сообщений.

Решение. , , при и

Проверяем условиеоптимальности кода , для r = 1

условие оптимальности принимает вид:

Вес каждой комбинации проверочной матрицы П

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

Окончательный вид матрицы С:

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

Задача 6.53. Построить порождающую матрицу группового кода (31; 26). Проанализировать, оптимален ли полученный код с точки зрения соотношения информационных и корректирующих разрядов.

Задача 6.54. Чем обусловливается минимальная граница возможного числа корректирующих разрядов при заданном числе информационных? Напишите 8 цифр, означающих длину оптимальных групповых кодов, способных при выполнении всех прочих условий корректировать одиночные сбои.

Задача 6.55. Источник сообщений рассчитан на передачу 120 различных одиннадцатиразрядных комбинаций. Одним из главных требований технического задания (ТЗ) на разработку приемного устройства является максимальная простота дешифратора и возможность коррекции одиночных ошибок в каждой передаваемой комбинации. Построить образующую матрицу группового кода, удовлетворяющую требованиям ТЗ.

Решение. Задана длина кода n = 11 и минимальное расстояние между кодами d₀ = 3. Согласно (62)

Минимальная простота дешифратора достигается при минимальном количестве сумматоров по модулю 2 в декодере, что возможно при минимальном весе комбинаций проверочной матрицы П. Для этого в качестве векторов, составляющих строки матрицы П, выбираем четырехзначные двоичные комбинации весом W_П = 2, 3, 4 (см. задачу 6.50) и используем те комбинации, в которых содержится меньшее число единиц, а именно: 0011; 0101; 1010; 1100; 0111.

Искомая матрица имеет вид:

Задача 6.56. Построить производящую матрицу группового кода с d₀ = 3, удовлетворяющего условию максимальной простоты кодера и декодера при передаче 1000 сообщений.

Задача 6.57.Построить групповой код по заданной производящей матрице:

Решение. Число строк матрицы n_И = 4. Следовательно, число возможных информационных комбинаций

1) 0000 5) 0010 9) 0001 13) 0011

2) 1000 6) 1010 10) 1001 14) 1011

3) 0100 7) 0110 11) 0101 15) 0111

4) 1100 8) 1110 12) 1101 16) 1111

Находим последовательно корректирующие разряды всех информационных комбинаций путем суммирования по модулю 2 тех

строк матрицы П, номера которых совпадают с номерами разрядов содержащих единицы в информационной части кода:

1) 000 2) 111 3) 110 4) 111

110

5) 101 6) 111 7) 110 8) 111

101101 110

010 011 101

9) 011 10) 111 11) 110 12) 111

011011

100 100

13) 101 14) 111 15) 110 16) 111

101 110

011 101

110 011011 101

001 000 011

Окончательно комбинации корректирующего кода имеют такой вид:

1) 0 0 0 0 0 0 0 9) 0 0 0 1 0 1 1

2) 1 0 0 0 1 1 1 10) 1 0 0 1 1 0 0

3) 0 1 0 0 1 1 0 11) 0 0 0 1 1 1 0

4) 1 1 0 0 0 0 1 12) 1 0 0 1 1 0 0

5) 0 0 1 0 1 0 1 13) 0 0 1 1 1 1 0

6) 1 0 1 0 0 1 0 14) 1 0 1 1 0 0 1

7) 0 1 1 0 0 1 1 15) 0 1 1 1 0 0 0

8) 1 1 1 0 1 0 0 16) 1 1 1 1 1 1 1

Задача 6.58. Какой вид имеют комбинации группового кода с d₀= 3, построенного для передачи четырехзначных двоичных комбинаций на все сочетания, если его порождающая матрица имеет вид:

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

Задача 6.60. Групповой код построен по матрице

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

Решение. Производящая матрица С в виде информационной матрицы И и проверочной матрицы П может быть представлена следующим образом:

Согласно правилу построения системы проверки (см. с. 96), система проверок для кодов, построенных С, будет иметь вид:

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

Если разряды синдрома соответствуют первому столбцу матрицы Н, т. е. , то ошибка в первом разряде принятой комбинации. Если синдром имеет вид 101, что соответствует второму столбцу матрицы Н, то ошибка во втором разряде и т. д. синдром 001 соответствует ошибке в третьем проверочном разряде кода.

Поскольку информационная часть кода обычно представляет собой натуральный двоичный код разрядности n_И, в качестве примера проверки корректирующих свойств кода используем информационные комбинации, соответствующие цифрам 3, 4 и 5 в четырехзначном двоичном коде[7]: 1100, 0010 и 1010. Значение корректирующих разрядов находим путем суммирования строк матрицы П, соответствующих единицам в информационных комбинациях:

Полные комбинации кода имеют вид соответственно: 1100110; 0010110; 1010101.

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

0100110, 0011110 и 1010100.

Находим проверочные векторы согласно системе проверок.

Для первой комбинации:

Синдром 011 показывает, что в первом разряде символ следует заменить на обратный.

Для второй комбинации:

синдром – 1 1 1, ошибка в четвертом разряде.

Для третьей комбинации:

синдром – 0 0 1, ошибка в седьмом разряде.

Задача 6.61. Какими способами можно проверить корректирующие способности кодов, построенных по заданным производящим матрицам?

Задача 6.62. Убедиться в том, что в кодовых векторах 1000111, 0110101, 1101001, 0000000 группового кода, построенного по следующей матрице:

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

Решение. Проверочная матрица П имеет вид:

соответствующая ей система проверок

Проверочная матрица Н имеет вид: , следовательно, ошибке в первом разряде соответствует синдром 111, во втором – 011, …, в седьмом –001.

Последовательно изменяем в исследуемых векторах по одному информационному разряду и по данной системе, проверок находим вид синдрома.

Правильный Ошибочные

1000111 0000111

I. II.

синдром –111. синдром –011

III. IV.

синдром – 110. синдром – 101.

Правильный Ошибочные

0110101 1110101

I. II.

синдром –111. синдром –011.

III. IV.

синдром – 110. синдром –101.

Правильный Ошибочные

1101001 0101001

I. II.

синдром – 111. синдром –011.

III. IV.

синдром –110. синдром –101.

Задача 6.101. Эквивалентны ли корректирующие способности кодов, построенных по следующим образующим матрицам С_15;11= и С_15;11=I₁₁ :

С_15;11=

Задача 6.102. Построить несколько комбинаций циклического кода с числом информационных разрядов n_и=11 и образующим многочленом х⁴+х³+1.

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