Введение в коды Рида-Соломона 0:01 Коды Рида-Соломона — помехоустойчивые коды, не троичные. Они являются циклическими и линейными блочными кодами. Рекомендуется посмотреть предыдущие ролики о циклических кодах и определении кодового расстояния.
Классификация кодов 1:01 Коды Рида-Соломона — частный случай блочных кодов. Блочные коды кодируются и декодируются независимыми блоками. Сверточные коды имеют память и являются потоковыми, а не блочными.
Табличные коды 2:10 Табличные коды имеют кодовую таблицу, показывающую соответствие между входным и выходным словами. Кодирующее устройство вносит избыточность в передаваемое сообщение. Табличные коды не требуют сложных математических операций.
Проблемы табличных кодов 4:02 Табличные коды становятся слишком большими при больших параметрах n и k. Устройства не могут хранить такие большие таблицы. Табличные коды редко используются для обнаружения и коррекции ошибок.
Линейные блочные коды 6:09 Линейные блочные коды используют порождающую матрицу размером n на k. Порождающая матрица должна быть линейно независимой. Линейные комбинации строк порождающей матрицы дают разные кодовые вектора.
Циклические коды 9:45 Циклические коды используют только первую строку порождающей матрицы. Остальные строки получаются путем циклического сдвига первой строки. Циклический сдвиг сохраняет все символы в кольце.
Порождающий полином 11:45 Порождающий полином определяет циклический код. Степень порождающего полинома равна числу проверочных символов r. Порождающий полином умножается на информационный полином для получения разрешенного полинома.
Фундаментальное свойство циклических кодов 14:18 Циклический сдвиг разрешенного кодового слова сохраняет его разрешенность. Это фундаментальное свойство циклических кодов.
Фундаментальное свойство циклических кодов 14:47 Циклические коды сохраняют разрешенные кодовые слова при сдвигах. Примеры: все нули, все единицы, все двойки, все пятерки. Циклические сдвиги не изменяют кодовые слова.
Кодовая таблица циклического кода 15:44 Кодовая таблица содержит все кодовые слова и их циклические сдвиги. Циклический код является линейным блочным кодом. Кодовая таблица замкнута относительно линейных операций и циклических сдвигов.
Коды Рида-Соломона 16:46 Коды Рида-Соломона являются особенными циклическими кодами. Они обеспечивают максимально возможное кодовое расстояние. Кодовое расстояние определяется как р + 1, где р — число проверочных символов.
Построение кодов Рида-Соломона 18:18 Коды Рида-Соломона позволяют выбрать кодовое расстояние и построить автоматический код. Для кодового расстояния 3, р должно быть равно 2. Для кодового расстояния 5, р должно быть равно 4.
Восьмеричный код Рида-Соломона 20:14 Основание кода выбирается равным п в степени ку, где п — простое число. Пример: п = 2, ку = 3, основание кода — 8. Восьмеричные символы обозначаются как икс-1, икс-2 и т.д.
Многомерность и векторы 20:58 Восьмеричный код можно рассматривать как трехмерный. Векторы состоят из ку элементов, где ку = 3. Количество векторов равно п в степени ку.
Порождающие полиномы 24:32 Циклические коды определяются порождающим полиномом. Порождающие полиномы следуют из разложения полинома на множители. Только определенные полиномы порождают циклические коды.
Пример кода Рида-Соломона 27:12 Кодовое расстояние выбрано равным 5. Требуемое число проверочных символов — 4. Получаем линейный блочный код 7-3 8-ричный.
Правила сложения и умножения элементов 28:08 Необходимо определить правила сложения и умножения элементов, таких как альфа в кубе и альфа в четвертом. Код является циклическим, и при умножении полиномов коэффициенты сворачиваются. Свертка — это сумма произведений элементов.
Понижение степени и линейная комбинация 28:40 Восьмеричное поле можно представить как 2^3. Нужно задать правила понижения степени, чтобы выразить альфа в степени ку в виде линейной комбинации альфа в меньшей степени. Цель — понизить степень до второй.
Специфические правила для кода Рида-Соломона 29:48 Разные правила дают разные коды. Для кода Рида-Соломона нужны специфические правила. Проверка правил показывает, что они обеспечивают код Рида-Соломона.
Вычисление степеней альфа 30:24 Вычисление степеней альфа: альфа в кубе, альфа в четвертом, альфа в пятом, альфа в шестом. Альфа в седьмой степени равна единице. Векторное представление элементов: единица, альфа, альфа в квадрате.
Выражение альфа в кубе через базисные элементы 31:23 Альфа в кубе выражается через базисные элементы. Базис состоит из трех векторов: единица, альфа, альфа в квадрате. Альфа в кубе выражается как единица плюс альфа.
Выражение альфа в четвертом через базисные элементы 32:28 Альфа в четвертом выражается как альфа плюс альфа в квадрате. Умножение на альфа соответствует сдвигу вправо на один символ. Базисные элементы остаются неизменными.
Выражение альфа в пятом через базисные элементы 34:10 Альфа в пятом выражается как альфа квадрат плюс альфа плюс один. Циклический сдвиг альфа в четвертом на один бит. Единица выходит за пределы вектора и размножается.
Выражение альфа в шестом через базисные элементы 35:59 Альфа в шестом выражается как единица плюс альфа в квадрате. Линейный сдвиг без переносов. Единица, выходящая за пределы регистра, превращается в ноль.
Проверка максимального периода 37:52 Альфа в седьмой степени равна единице, что подтверждает максимальный период. Все векторы разные, без дубликатов. Максимальный период кода Рида-Соломона — семь.
Таблица сложения 40:32 Пример сложения альфа-квадрат и альфа-четвертое. Подстановка двоичных векторов вместо альфа-квадрат и альфа-четвертое. Сложение по модулю два и возврат к альфа-степени один.
Умножение и степени 41:29 Пример умножения альфа-квадрат на альфа-четвертое. Использование семерки как модуля для степеней. Вычитание семерки из степени для получения альфа-четвертой.
Построение таблиц 42:34 Перебор возможных вариантов для построения таблиц сложения и умножения. Пример заполнения таблицы сложения.
Симметричная матрица 43:36 Таблица сложения как симметричная матрица. Заполнение верхнего треугольника матрицы. Диагональные элементы равны нулю.
Таблица умножения 46:36 Пример заполнения таблицы умножения. Геометрическая прогрессия степеней альфа. Зацикливание степеней по кольцу.
Обратные элементы 49:44 Определение обратного элемента по умножению. Пример вычисления обратного элемента для альфа-квадрат. Единственность обратного элемента для всех элементов.
Обратные элементы по сложению 51:40 Пример обратного элемента по сложению для альфа-четвертое. Правило для однозначности таблиц и корректности операций. Взаимная однозначность операций сложения и умножения.
Порождающий полином кода Рида-Соломона 52:29 Порождающий полином кода Рида-Соломона имеет степень, равную числу элементов кода. Для кода с длиной 7 и числом элементов 4, полином имеет степень 4. Полином можно факторизовать на 4 множителя: x - x1, x - x2, x - x3, x - x4.
Разложение полинома и выбор поля 54:29 Поле выбирается по степени, обеспечивающей максимальный период. Полином x^n - 1 раскладывается на произведение степеней альфа от 0 до n-1. Для кода Рида-Соломона степени альфа должны возрастать на единицу.
Требования к порождающему полиному 57:08 Порождающий полином должен состоять из r подряд идущих со-множителей. Степени альфа должны возрастать последовательно. Кодовое расстояние кода Рида-Соломона равно r + 1.
Пример порождающего полинома 1:00:44 Пример полинома: α^3 + αx + 1x^2 + α^3x^3 + 1x^4. Вектор, соответствующий полиному, дополняется нулями до 7 элементов.
Кодирование и эквивалентность двоичному коду 1:02:02 На вход поступает 3 трехбитовых символа, на выходе получается 7 трехбитовых символов. Код Рида-Соломона эквивалентен двоичному коду 21-9. Дополнительные степени свободы позволяют достичь максимального кодового расстояния.
Корни порождающего полинома 1:04:37 Порождающий полином имеет 4 корня: α, α^2, α^3, α^4. α^7 = 1 имеет 7 значений, соответствующих корням седьмой степени из единицы. Эти значения соответствуют различным степеням альфа.
Различие корней 1:07:19 Все 7 значений корней различны. Единица в любой степени равна единице, поэтому все степени альфа являются корнями. Степени альфа не равны друг другу, что обеспечивает уникальность элементов кода.
Определение проверочного полинома 1:08:34 Порождающий полином определен. Проверочный полином можно определить через циклический код. Умножение порождающего полинома на проверочный дает ноль.
Разложение на множители 1:09:06 Разложение числителя на множители. Корни: x - 1, x - α^5, x - α^6. Полиномы дополняют друг друга.
Результат и вектор проверочного полинома 1:09:45 Результат: α^4 + α^2x + α^3x^2 + x^3 + x^3. Вектор проверочного полинома: α^4, α^2, α^3, 1, 0, 0, 0.
Свертка коэффициентов 1:10:39 Произведение полиномов соответствует свертке коэффициентов. Вектор можно записать задом наперед для упрощения свертки.
Циклический сдвиг и скалярные произведения 1:12:14 Умножение вектора на реверсивный вектор. Циклический сдвиг влево на один бит. Скалярные произведения должны быть равны нулю.
Кодирование кода Рида-Соломона 1:15:30 Кодирование по способу Рида-Соломона. Информационный полином и его значения при различных степенях α. Объединение значений полинома дает разрешенное кодовое слово.
Пример кодирования 1:19:52 Пример с k = 3, n = 7, p = 4. Информационный вектор: 3 единицы. Информационный полином: 1 + x + x^2. Кодовое слово: 7 восьмеричных символов.
Вычисление значений полинома 1:21:23 Вычисление значений полинома при различных степенях α. Использование таблицы сложения. Кодовое слово принадлежит коду Рида-Соломона.
Проверка кодового слова кода Рида-Соломона 1:23:41 Умножение полинома на проверочный полином. Разделение умножения на части для удобства. Умножение вектора на скаляр.
Умножение полиномов и циклический сдвиг 1:24:41 Умножение полиномов с учетом степеней. Циклический сдвиг вектора для умножения на икс. Замена старших степеней на нулевые.
Проверка результата умножения 1:28:19 Сложение полиномов с использованием таблицы сложения. Подтверждение, что результат равен нулю. Подтверждение принадлежности вектора к коду Рида-Соломона.
Деление полиномов и проверка кодового слова 1:29:50 Деление полинома на проверочный полином. Проверка, что частное равно нулю. Подтверждение, что вектор является разрешенным кодовым словом.
Порождающая матрица кода Рида-Соломона 1:34:06 Описание порождающей матрицы циклического кода. Преобразование циклической матрицы в систематическую форму. Эквивалентные преобразования и сохранение линейной независимости строк.
Взаимно однозначное соответствие кодовых слов 1:37:04 Сравнение множеств разрешенных кодовых слов. Подтверждение взаимно однозначного соответствия. Эквивалентность двух матриц и кодов.
Кодовое расстояние кода Рида-Соломона 1:38:38 Код Рида-Соломона обеспечивает максимальное кодовое расстояние. Размер матрицы и кодовое расстояние. Доказательство максимального кодового расстояния.
Определение кодового расстояния 1:39:41 Кодовое расстояние определяется как минимальный отличный от нуля вес. Вес кодового слова — это количество ненулевых элементов. Минимальный отличный от нуля вес среди всех кодовых слов является кодовым расстоянием.
Систематическая форма матрицы 1:40:12 Матрица записана в систематической форме. Гарантировано к минус один нулей и одна единица. Вес строк минимизирован, кодовое расстояние равно количеству ненулевых элементов.
Порождающая матрица и кодовая таблица 1:41:14 Строки порождающей матрицы являются разрешенными кодовыми словами. Кодовое расстояние частично оценивается по порождающей матрице.
Линейные коды и их кодовое расстояние 1:41:40 Кодовое расстояние линейных кодов не превышает р плюс один. В систематической форме все элементы, кроме одного, нулевые.
Коды Рида-Соломона 1:42:50 Все элементы подматрицы кода Рида-Соломона ненулевые. Все определители второго и третьего порядка также ненулевые.
Линейная независимость и кодовое расстояние 1:47:02 Линейная независимость строк обеспечивает максимальное кодовое расстояние. Два элемента не могут обнулиться одновременно.
Заключение 1:48:55 Кодовое расстояние кода Рида-Соломона строго равно р плюс один. Следующая тема будет посвящена декодированию кода Рида-Соломона.
