Все векторы x in b n имеющие один синдром образуют
Главная / Образование /
Основы информационных технологий / Тест 7
Упражнение 1:
Номер 1
Какой тип ошибок при передаче сообщения встречается наиболее часто?
Ответ:
 (1) замена знака 
 (2) вставка знака 
 (3) пропуск знака 
Номер 2
Какой метод повышения надежности передачи данных использует человек, который пытаясь передать по телефону с плохой слышимостью слово “СЛОН”, сказал “Степа, Лена, Оля, Николай”?
Ответ:
 (1) передача в контексте 
 (2) дублирование сообщений 
 (3) передача с переспросом 
 (4) оптимальная передача 
Номер 3
Какой метод повышения надежности использует человек, который не может расшифровать сообщение и просит у источника повторить его еще раз?
Ответ:
 (1) передача в контексте 
 (2) дублирование сообщений 
 (3) передача с переспросом 
 (4) оптимальная передача 
Упражнение 2:
Номер 1
Какие коды используются для введения избыточности с целью дальнейшего обнаружения и исправления ошибок?
Ответ:
 (1) коды Фано 
 (2) блоковые коды 
 (3) сверточные коды 
 (4) оптимальные коды 
Номер 2
Допустим, кодовые слова кода c содержат четное число единиц. Сколько ошибок можно обнаружить, проверяя четность единиц во входящих сообщениях?
Ответ:
 (1) 1 
 (2) 2 
 (3) четное число ошибок 
 (4) нечетное число ошибок 
Номер 3
Код “Тетраэдр” не способен обнаружить:
Ответ:
 (1) 1 ошибку 
 (2) 3 ошибки 
 (3) четное число ошибок 
 (4) нечетное число ошибок 
Упражнение 3:
Номер 1
Вычислите расстояние Хемминга между словами a=11010 и b=11101 пространства B5.
Ответ:
 (1) 1 
 (2) 2 
 (3) 3 
 (4) 4 
Номер 2
Как называется характеристика кода, которая отражает его возможность обнаруживать и исправлять ошибки?
Ответ:
 (1) линейность 
 (2) оптимальность 
 (3) кодовое расстояние 
 (4) векторное расстояние 
Номер 3
Кодовым расстоянием кода с является:
Ответ:
 (1) максимальное расстояние между различными кодовыми словами 
 (2) минимальное расстояние между различными кодовыми словами 
 (3) длина самого длинного кодового слова 
 (4) длина самого короткого кодового слова 
Упражнение 4:
Номер 1
Если имеется кодовое слово a, а слово b получилось из a в результате 2 ошибок, то расстояние Хэминга между словами:
Ответ:
 (1) 0 
 (2) 1 
 (3) 2 
 (4) 4 
Номер 2
Код обнаруживает 2 ошибки, если для любых кодовых слов a и b:
Ответ:
 (1) вероятности их появления равны 
 (2) расстояние Хэминга больше или равно 3 
 (3) расстояние Хэминга больше или равно 2 
 (4) расстояние Хэминга меньше или равно 3 
Номер 3
Код исправляет 2 ошибки, если для любых кодовых слов a и b:
Ответ:
 (1) расстояние Хэминга больше или равно 3 
 (2) расстояние Хэминга меньше или равно 3 
 (3) расстояние Хэминга больше или равно 5 
 (4) расстояние Хэминга меньше или равно 5 
Упражнение 5:
Номер 1
Согласно линейной алгебре 1+1 будет равно
Ответ:
 (1) 0 
 (2) 1 
 (3) 2 
 (4) 4 
Номер 2
В поле GF(2) вектор a сложенный с самим собой будет равен:
Ответ:
 (1) 0 
 (2) 1 
 (3) a 
 (4) 2a 
Номер 3
Как называется совокупность различных сумм векторов в Bn поля GF(2)?
Ответ:
 (1) линейная комбинация 
 (2) линейная зависимость 
 (3) линейная оболочка  
 (4) линейная совокупность 
Упражнение 6:
Номер 1
Векторы в Bn поля GF(2) линейно зависимы, если существует сумма некоторых из них, равная :
Ответ:
 (1) 0 
 (2) 1 
 (3) 2 
 (4) линейной оболочке 
Номер 2
Векторы в Bn поля GF(2) линейно независимы, если любая сумма некоторых из них не равна: :
Ответ:
 (1) 0 
 (2) 1 
 (3) 2 
 (4) линейной оболочке 
Номер 3
Если векторы в Bn поля GF(2) линейно независимы, то все их линейные комбинации (суммы):
Ответ:
 (1) равны нулю 
 (2) равны единице 
 (3) одинаковы 
 (4) различны 
Упражнение 7:
Номер 1
Сколько различных комбинаций можно составить из n линейно независимых векторов?
Ответ:
 (1) n 
 (2) n2 
 (3) 2n 
 (4) 2n 
Номер 2
Сколько различных комбинаций можно составить из 3 линейно независимых векторов?
Ответ:
 (1) 3 
 (2) 6 
 (3) 8 
 (4) 9 
Номер 3
Сколько векторов содержит линейная оболочка 3 линейно независимых векторов?
Ответ:
 (1) 3 
 (2) 6 
 (3) 8 
 (4) 9 
Упражнение 8:
Номер 1
Как называется подмножество векторов из векторного пространства Bn , замкнутое относительно операций сложения и умножения на число из поля GF(2)?
Ответ:
 (1) подпространство 
 (2) комбинация 
 (3) оболочка 
 (4) зависимость 
Номер 2
Как называется число единичных координат вектора?
Ответ:
 (1) норма вектора 
 (2) пространство вектора 
 (3) степень вектора 
 (4) длина вектора 
Номер 3
Как называется матрица, столбы которой образуют базис пространства решений системы Hx=0?
Ответ:
 (1) комбинаторная 
 (2) начальная 
 (3) порождающая 
 (4) единичная 
Упражнение 9:
Номер 1
Линейный код c проверочной матрицей Hc имеет кодовое расстояние pcs s+1 тогда и только тогда, когда …
Ответ:
 (1) любые s столбцов матрицы линейно зависимы 
 (2) любые s столбцов матрицы линейно независимы 
 (3) любые 2 столбца матрицы линейно зависимы 
 (4) только 2 столбца матрицы линейно зависимы 
Номер 2
Линейный код c с проверочной матрицей Hc имеет кодовое расстояние pcs4 тогда и только тогда, когда …
Ответ:
 (1) любые 3 столбца матрицы линейно зависимы 
 (2) любые 3 столбца матрицы линейно независимы 
 (3) любые 2 столбца матрицы линейно зависимы 
 (4) любые 2 столбца матрицы линейно независимы 
Номер 3
В линейном коде с повторением слово передано неправильно, если:
Ответ:
 (1) число единичных разрядов в принятом слове нечетно 
 (2) число единичных разрядов в принятом слове четно 
 (3) не все разряды в нем одинаковы 
 (4) все разряды в нем одинаковы 
Упражнение 10:
Номер 1
Все векторы , имеющие один синдром, образуют:
Ответ:
 (1) группу 
 (2) подпространство 
 (3) класс 
 (4) разряд 
Номер 2
Какой вектор называется лидером класса?
Ответ:
 (1) вектор с минимальным весом из векторов с одним синдромом 
 (2) вектор с максимальным весом из векторов с одним синдромом 
 (3) вектор с минимальным весом из векторов с разными синдромами 
 (4) вектор с максимальным весом из векторов с разными синдромами 
Номер 3
Согласно методу декодирования линейного кода по синдрому декодирование осуществляется:
Ответ:
 (1) сложением принятого вектора с лидером класса 
 (2) умножением принятого вектора и лидера класса 
 (3) вычитанием из принятого вектора лидера класса 
 (4) вычитанием из лидера класса принятого вектора 
Источник
Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 21:59, 14 мая 2016.
Определение
Определение «Определение – Cиндром вектора» |
|---|
Пусть – проверочная матрица: для Пусть – произвольный вектор. – синдром (не зависит от исходного кодового слова). |
Поскольку рассматриваемый код — это нулевое пространство матрицы (т.е. пространство векторов, каждый из которых ортогонален проверочной матрице), то некоторый вектор является кодовым словом тогда и только тогда, когда его синдром равен нулю. Вообще, каждой строке матрицы соответствует проверочное соотношение, которому должны удовлетворять кодовые слова. Компоненты вектора равны нулю для , и не равны нулю для всех остальных.
, где:
– ошибка,
– кодовое слово с ошибкой.
Смежные классы, синдром смежного класса. Лидеры смежного класса
абелева группа, где – подгруппа.
Введем смежный класс по аддитивной подгруппе .
Заметим:
– синдромы совпадают для всех векторов из одного и того же класса смежности.
Теорема Теорема о синдроме смежного класса |
|---|
Два вектора и принадлежат одному и тому же смежному классу тогда и только тогда, когда их синдромы равны. |
Доказательство |
Два элемента группы и принадлежат одному и тому же смежному классу тогда и только тогда, когда есть элемент подгруппы, которой в данном случае является кодовое векторное пространство. Если кодовое пространство — это нулевое пространство матрицы , то вектор принадлежит кодовому пространству тогда и только тогда, когда: Поскольку для умножения матриц справедлив дистрибутивный закон, то Т.о. вектор является кодовым вектором тогда и только тогда, когда синдромы векторов и равны. ч.т.д. |
Синдромов столько же, сколько существует смежных классов:
Декодирование по синдрому. Стандартное расположение линейного кода
Пусть — линейный -код, — нулевой вектор и — остальные кодовые векторы. Тогда таблицу декодирования можно составить следующим образом. Кодовые векторы располагаются в виде строки с нулевым вектором слева. Затем один из оставшихся наборов длины , например , помещается под нулевым вектором. (Обычно это бывает один из наборов, которые наиболее вероятно получить на выходе, если по каналу передавался нулевой вектор.) Далее строка заполняется так, чтобы под каждым кодовым вектором – помещался вектор . Аналогично в первый столбец второй строки помещается вектор и строка заполняется таким же способом. Процесс продолжается до тех пор, пока каждый возможный набор длины не появится где-нибудь в таблице. Это стандартное расположение, конечно, в точности совпадает с таблицей смежных классов. Строки являются смежными классами, а векторы в первом столбце — образующими смежных классов.
Пусть передавался вектор , а получен вектор .
Если , где – — образующий -го смежного класса, то вектор должен находиться в стандартном расположении в -м смежном классе под кодовым словом и и поэтому будет правильно декодирован. Если же вектор не является образующим смежного класса, то вектор должен находиться в некотором смежном классе, например -м, с образующим . Тогда вектор расположен в -й строке, но не под вектором , потому что .
Процесс декодирования может быть значительно упрощен за счет использования таблицы декодирования:
Таблица строится так, что в ней приводятся образующие смежных классов и синдромы для каждого из смежных классов. После того как получен вектор, вычисляется его синдром. Затем по таблице отыскивается образующий смежного класса, являющийся предполагаемым набором ошибок; вычитание его из полученного вектора дает предположительно посланный кодовый вектор. Хотя в большинстве случаев такая процедура во много раз уменьшает требования к объему памяти при осуществлении декодирования, этот объем все-таки может быть очень большим. Например, для двоичного (100,80)-кода требуется таблица декодирования с входами, что конечно, далеко выходит за пределы разумного. Число смежных классов равно — величине, много меньшей, но тем не менее все еще совсем нереальной.
Теорема Утверждение |
|---|
Пусть — линейный двоичный -код (т. е. групповой код), используемый для передачи по двоичному симметричному каналу. Предположим, что все кодовые векторы имеют одну и ту же вероятность быть переданными. Тогда средняя вероятность правильного декодирования совпадает с наибольшей возможной для этого кода, если в качестве таблицы декодирования используется стандартное расположение, в котором каждый образующий смежного класса имеет минимальный вес в своем классе. |
Доказательство |
Обозначим через вектор, стоящий в -й строке и -м столбце таблицы декодирования. Кодовое слово в верхней строке столбца обозначим через ,-. Обозначим через расстояние Хэмминга между полученным вектором и кодовым словом , в которое он преобразуется при декодировании. Тогда вероятность правильного декодирования, если было передано слово , равна где — вероятность ошибки в канале, a . Поскольку имеется кодовых слов, которые предполагаются равновероятными, то при осреднении вероятности правильного декодирования используется весовой множитель : Каждому возможному двоичному вектору на выходе в этой сумме соответствует одно слагаемое, и каждое из этих слагаемых принимает максимальное значение, если соответствующий вектор декодируется в ближайший кодовый вектор в смысле Хэмминга, так как есть монотонно убывающая функция от . Поэтому вероятность правильного декодирования будет максимальной, если каждый полученный вектор будет преобразовываться в ближайший кодовый вектор. Предположим теперь, что некоторый вектор расположен в таблице декодирования под кодовым вектором , так что расстояние Хэмминга между ними равно . Допустим, что ближайший кодовый вектор находится на расстоянии . Пусть — образующий смежного класса, содержащего вектор . Тогда вес вектора равен . Элемент имеет вес и лежит в том же самом смежном классе. Поскольку предполагалось, что имеет минимальный вес в своем смежном классе, то , и поэтому лежит по крайней мере так же близко к , как и к . Число образующих смежных классов веса обозначим через . Вероятность правильного декодирования может быть записана тогда следующим образом: |
Литература
Мак-Вильямс Ф. Дж, Слоэн Н. Дж. А. Теория кодов, исправляющих ошибки: Пер. с англ. — М. : Связь, 1979. — С. 744, ил.
Источник