Задача построения ЛГК с заданными свойствами.

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

задача построения лгк с заданными свойствами .

Алгоритм:

1)если N заданная мощность кода, то информационная часть матрицы имеет размер k=]log₂N[. 2) любой проверочный столбец является суммой по mod 2 некоторого количесва столбцов информационной части матрицы, при этом каждый столбец информационной части должен хотя бы раз принять участие повереностью столбца.

3) вес каждой строки должен быть ω_i≥d_min .

4) расстояние по Хеммингу ρ(V_i,V_j)≥d_min.

Пример: построить порождающую матрицу. N=16, b=2.

K=lod₂16=4, d_min ≥b+1=3.

Полученная матрица не удовлетворяет условию задания, потому вес V₂, V₄=2.

ρ(V₁,V₂)=2, ρ(V₃,V₄)=2.

Вывод: данная матрица не удовлетворяет условию.

128→16 слов.

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

Рассмотрим:

 256→16 слов.

G₁=>(7,4), G₂=>(8,4). Об этом говорит сайт https://intellect.icu . Сравнивая G₁ и G₂, можно сделать вывод: G₁ порождает код, имеющий скорость R=k/n=4/7, тогда как G₂R=1/2. Код, порождаемый G₁ более выгодный.

Определение требуемого количества проверочных столбцов.

Коррекция ошибок основана на избыточности. Избыточными являются разряды проверочной части матрицы G. Прежде чем определить минимально необходимое количество проверочных разрядов установим связи, которые необходимо накладывать на проверочные и информационные разряды, чтобы обеспечить заданную корректирующую способность кода. Рассмотрим это на G₁.

p₁=a₁(+)a₂(+)a₄, p₂=a₁+a₃+a₄, p₃=a₂+a₃+a₄,

p₁+a₁+a₂+a₄=S₁, p₂+a₁+a₃+a₄=S₂, p₃+a₂+a₃+a₄=S₃.

Вектор S(S₁,S₂,S₃) — вектор синдромов — указатель на наличие ошибок.

Если ошибок нет, то S(S₁,S₂,S₃)=0, в противном случае если совершено не более t ошибок, то S≠0.

 d_min≥2t+1 => t=1. Как следует из таблицы все векторы S при наличие одиночной

ошибки ≠0 и различны, т.е. каждая комбинация S однозначно указывает номер

ошибочного разряда. Для коррекции этого разряда достаточно

проинвертировать.

Пример: допустим, что в слове имеется 2 ошибки, построим таблицу синдромов для этой ошибки.

Как следует из этой таблицы все синдромы ≠0. Однако для некоторых комбинаций отказов или ошибок синдромы повторяются, поэтому нельзя однозначно сказать какие именно пары разрядов ошибочны. Т.о. рассмотренный код может обнаруживать 2 ошибки, но исправлять только одну. Те не менее, на самом деле обнаруживаются не тока парные ошибки, трехкратные ошибки. Не обнаруживаются

только 4 из 20 возможных. Четырехкратные : 4 из 15 возможных. Обнаруживаются любая 5 и 6 кратные ошибки. Т.о., из всех 63 возможных комбинаций ошибок не обнаруживаются только 8.

Для данного кода количество проверочных столбцов равно 3 и следовательно составлено 3 проверочных уравнения для построения трехкомпонентного синдрома S. В общем случае количество уравнений должно быть ≥ количеству исправляемых ошибок. Если имеется m проверочных разрядов, то 2^r-1 это количество возможных различных проверочных комбинаций на r разрядах. Их число должно быть ≥ количеству исправляемых ошибок. Если мв хотим исправить одиночные ошибки (t=1), то 2^r-1=С¹_n, если две, то 2^r-1≥С¹_n+С²_n. В общем случае: 2^r-1≥С¹_n+С²_n+…+С^t_n.

Пример: r=n-k, 2^r-n≥С¹_n+С²_n+…+С^t_n , k=4, t=1: 2^n-4≥С¹_n+1, 2^n-4≥n+1, n-4≥]log₂(n+1)[.

n=6: 2≥]log₂(7)[ - не подходит

n=7: 3≥]log₂(8)[, r=3 => n≥] log₂ n(n+1)/2+1[+4, n=10.

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