Теорема (граница Хемминга)
Доказательство: Пусть V – наш код, V’ – шар радиуса t, тогда в это шаре расстояние между двумя любыми точками Таких множеств // По определению
Теорема (граница Джоши) Доказательство: Пусть V – код с расстоянием d,
Теперь получим оценку снизу.
![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]()
Теорема (Варшамова-Гильберта) Доказательство: Построим код V* следующим образом:
1) x 1 → V* 2) x 2 → V* \ St (x’) … p- 1 точка кода. p) xp → V* \
В какой-то момент сделать это не сумеем. Расстояние между любыми точками таким образом построенного кода равняется 2 t, откуда и следует неравенство.
Теорема (Плоткина) Доказательство: Рассмотрим код k 1 k 2 k n – количество единиц в каждом столбце. Рассмотрим сумму расстояний между всеми кодовыми словами. Здесь каждое расстояние подсчитано 2 раза. Тогда max x (S-x) достигается при x = S /2. Воспользуемся этим.
Хотим, чтобы Теорема Шеннона для канала с шумом. Факты из теории вероятности.
Теорема (неравенство Чебышева) Испытание Бернулли, вероятность успеха p (неудача 1- p). Есть n испытаний. Тогда Доказательство: Схема кодирования и декодирования. Вспомогательные утверждения. Если передается слово из n 0 и 1, то
1) Есть код C = { x 1… xm } – кодовые слова 2) Применяем декодирование в ближайшее слово (по наибольшему правдоподобию)
a x 1 T(C) – таблица b x 2 … … … xM
3) Вероятность ошибки декодирования P (x) – вероятность неправильного декодирования x Pc (характеристика кода C) = 1\ M ∑ P (x) Число различных кодов в Bn: Пусть L – множество таких кодов. ρ (x) – вероятность правильного декодирования. ρс = 1\ M ∑ ρ (x) Pc + ρс = 1 P *(M, n, p) = min Pc → P *(M, n, p) ≤ На сегодняшний день наилучший код не найден, все существующие отличны от него в константу раз. Лемма ( Доказательство: | S[pn] (x)| = Вспомним, что 0 ≤ p < 1\2, принцип – декодирование в ближайшее, (1 – p)n ≥ p(1 – p)n-1 ≥ … ≥ pk(1-p)n-k
Тогда | S [ pn ](x)| ≤ (p [ pn ] (1 – p) n – [ pn ])-1 = xi → канал → Y Считаем, что Y = x i + e, e – вектор ошибок τ – случайная величина = | e | (количество ошибок) Т.к. источник Бернулли, то E (τ) = np, D (τ) = np (1 – p) b = Лемма ( Доказательство: Применим неравенство Чебышева: P {| τ – E (τ)| > ε } ≤ D (τ)\ ε 2 ρ = [ E (τ) + b] P {| τ – nP | > b} ≤ D (τ) \ b 2 P {| τ – nP | > b } ≤ ε \2 P (τ > ρ) = P {| τ – nP | > b } – проверим это:
- τ np τ τ > nP + b τ – nP > b Лемма ( Доказательство: Из леммы ( | Sρ (x)| ≤ 2 nH (ρ \ n ). Домножим на log и поделим на n.
1\ n log | Sρ (x)| ≤ H(ρ \ n) = - ρ \ n log ρ \ n – (1 – ρ \ n) log (1 – ρ \ n) = - [ nP + b ]\ n log [ nP + b ]\ n – (1 – [ nP + b ]\ n ] log (1 – [ nP + b ]\ n) ≈ - P log P – (1 – P) log (1 – P) – O(b \ n) = O(n -1\2)
(1) (2) Вероятностное доказательство теоремы. Теорема Шеннона: для любого R: 0 < R < C (ρ) P *(M, n, P) → 0, n → ∞ Доказательство: Пусть передаем x i, принято некое y, оцениваем ошибку декодирования. Ошибочное декодирование:
![]() ![]() ![]()
![]() ![]() ![]()
Кодовые точки упали как угодно, на них строим шар радиуса ρ. Декодируем так: если точка у попала в шарик радиуса ρ вокруг кодовой точки, то декодируем ее в данную кодовую точку, если в этом шаре нет других точек; если есть, то у декодируем в произвольно заданную точку. Это будет ошибкой. Вводим функцию (1), тогда вероятность ошибки оценивается суммой (2) Применяем лемму ( 1\ n log (P *(M, n, P) – ε \2) ≤ 1\ n log | Sρ | M \2 n = 1\ n log | Sρ |2 Rn - n ≤ R – C (ρ) – 1 – O(n -1\2) + 1 → P *(M, n, P) < ε \2 + 2- δn. Теорема доказана.
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|