Меню
Главная
Авторизация/Регистрация
 
Главная arrow Математика, химия, физика arrow ДИСКРЕТНЫЙ АНАЛИЗ. ОСНОВЫ ВЫСШЕЙ АЛГЕБРЫ
Посмотреть оригинал

Коды Рида - Маллера

Приведем еще одну оценку для кодового расстояния.

Теорема 4.20 (граница Плоткина). Кодовое расстояние d любого q-ичного кода длины п, содержащего qk кодовых слов, удовлетворяет iiejmeencmey

Доказательство. Минимальное расстояние между кодовыми словами не превосходит среднего расстояния:

Оценим, какой вклад в сумму вносит каждая позиция в кодовом слове. Для этого нужно оценить количество пар слов, различающихся в позиции i. Обозначим через F множество символов кода, а для каждого i через /а,г количество кодовых слов, у которых в позиции i стоит а е F. Тогда ясно, что J2aeF /<М = Qk-> а количество пар слов, различающихся в г-й позиции, равно

11ри заданной сумме чисел сумма квадратов этих чисел достигает минимума, когда все числа равны. Поэтому вклад каждой позиции не превосходит

Отсюда получаем искомую оценку

Если q является степенью простого числа, граница Плот- кина достигается на кодах Рида - Мал лера первого порядка. Возьмем п = qm 1. Тогда слову длины п можно однозначно сопоставить функцию Fm {0} —» F. Код Рида - Маллера первого порядка образуют такие слова, которым соответствуют линейные однородные функции и 0. Количество кодовых слов также равно q,n (линейная однородная функция задается т коэффициентами). Поскольку любая отличная от 0 линейная однородная функция принимает нулевое значение ровно в <7m_1 точках, кодовое расстояние для кода Рида - Маллера первого порядка равно d = qm — qm~l. Граница Плоткина в этом случае имеет вид

 
Посмотреть оригинал
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы