Методы эффективного помехоустойчивого кодирования. Общий принцип использования избыточности

Кодирование, с помощью которого можно устранять ошибки обусловленные наличием шума в канале называется помехоустойчивым. Коды способные исправлять и обнаруживать ошибки называется помехоустойчивым кодом. К сожалению основная теорема кодирования Шеннона не конструктивна, она не указывает способ построения конкретного оптимального помехоустойчивого кода, обеспечивающего предельное согласование сигнала с каналом, существование которого доказывает. Вместе с тем обосновав принципиальную возможность построения помехоустойчивых кодов, обеспечивающих идеальную передачу. Теория Шеннона мобилизовала усилия ученых на разработку конкретных кодов. В результате в настоящее время теория помехоустойчивого кодирования превратилась в самостоятельную науку в развитии которой достигнуты большие успехи.
Рассмотрим основополагающие принципы заложенные в основу построения помехоустойчивых кодов. Как следует из доказательства основной теоремы Шеннона неприменимым свойством помехоустойчивых кодов является наличие избыточности. При этом необходима не просто любая избыточность, а специфическая, определяемая свойствами канала и правилом построения кода. И позволяющая с минимальными затратами повысить вероятность передачи. В ситуации когда источник сообщений обладает собственной существенной избыточностью, которая в принципе тоже в определенной степени повышает достоверность передачи информации, но не так эффектно как это возможно. Поступают следующим образом: сначала с помощью эффективного кодирования до минимума уменьшают избыточность источника сообщений, а затем в процессе помехоустойчивого кодирования вносят в передаваемый сигнал избыточность, позволяющую простыми средствами поднять верность. Таким образом эффективное кодирование может сочетаться с помехоустойчивым. Помехоустойчивые коды можно подразделить на два больших класса блочные и непрерывные. В случае блочных кодов, при кодировании, каждому дискретному сообщению ставится в соответствие отдельный блок кодовых символов называемого кодовой комбинацией. Непрерывные коды образуют последовательность символов неразделяемых на кодовые комбинации. Рассмотрим принцип построения помехоустойчивых блочных кодов. Избыточность обуславливающая корректирующие свойства равномерного блочного кода обычно вводится за счет выполнения неравенства mⁿ M (2.29), где m-основание кода т.е. объем алфавита используемых кодовых символов, n-длина или количество разрядов кодовой комбинации, М-количество сообщений подлежащих кодированию. Выполнение этого неравенства означает, что для передачи знаков сообщения используют лишь часть М возможных кодовых комбинаций. Используемые кодовые комбинации называют разрешенными. Неиспользуемые mⁿ -M комбинации являются запрещенными. На вход канала подаются только разрешенные комбинации. Если вследствие помех один или несколько символов приняты ошибочно, то на выходе канала появляется запрещенная комбинация, что и говорит о наличии ошибки. Для того, чтобы обеспечить выполнение (2.29) необходимо выбирать n  K, где K - минимальное целое, удовлетворяющее неравенству m^K³M (2.30). Число K обычно называют количеством информационных разрядов кодовой комбинации, поскольку именно столько разрядов должна содержать комбинация кода с основанием m, чтобы число разных кодовых комбинаций было не меньше числа сообщений М подлежащих передаче. R=n-K разрядов кодовой комбинации необходимых для передачи полезной информации называются проверочными. Количество их и определяет избыточность помехоустойчивого кода. При использовании помехоустойчивого кода возможно декодирование с обнаружением и исправлением ошибок. В первом случае на основе анализа принятой комбинации выясняется, является ли она разрешенной или запрещенной. После этого запрещенная комбинация либо отбрасывается, либо уточняется путем посылки запроса на повторение переданной информации. Во втором случае при приеме запрещенной комбинации определенным способом выявляются и исправляются содержащиеся в ней ошибки. Максимальные числа ошибок в кодовой комбинации q и S которые могут быть обнаружены (q) или исправлены (S) с помощью данного кода называются соответственно обнаруживающей или исправляющей способностью кода. В значении q и S определяются величиной d_min минимальным кодовым расстоянием между ближайшими разрешенными комбинациями. Под кодовым расстоянием понимают количество неодинаковых разрядов в кодовых комбинациях. Величина d_min в помехоустойчивом коде зависит от соотношения n и К т.е. от числа r проверочных разрядов кода. Рассмотрим информационный (т.е. базирующий на идеях Теории Информации) подход позволяющий оценить необходимую минимальную избыточность, выраженную в количестве проверочных разрядов r_min блочного помехоустойчивого кода длиной n с заданной исправляющей способностью S. Пусть имеется код с основанием m и с исправляющей способностью S. И используется декодирование с исправлением ошибок. На приеме при использовании такого кода возможно две ситуации: правильный прием сообщения и неправильный. Осуществление с вероятностью P_H. Неправильный прием может произойти в том случае, когда из-за превышения числом ошибок пришедшей из канала кодовой комбинации значение S она может превратиться в одну из других разрешенных кодовых комбинаций. В свою очередь правильный прием осуществляется либо в том случае, когда в принимаемой комбинации отсутствуют ошибки (обозначим вероятность такого сообщения Р₀), либо N_прав в случаях когда в принятой комбинации присутствуют ошибки которые могут быть исправлены рассмотренным кодом. Вероятности таких случаев обозначим через P_j j=1  N_прав. Для решения поставленной задачи определим минимальное количество информации, которой может быть описана совокупность событий, включающая появление одной из конкретных ошибок и отсутствие ошибок или появление некорректных ошибок. Зная эту величину и максимальное количество информации которое может содержать один проверочный символ кода можно определить минимальное число проверочных символов. Количество информации необходимо для описания указанных событий I_K=_j=0^NnnP_jlogP_j-P_HlogP_H (2.31) (в случае отсутствия ошибки учтем включением нуля в предел суммирования). Максимальное количество информации которое может содержать символ кода с основанием m в соответствии с (1.6) равно log₂m. Следовательно число проверочных разрядов в комбинации кода не может быть меньше, чем r_min=I_K/log₂m (2.32). Определенную таким образом величину r_min называют информационным пределом избыточности. Найдем значение r_min для двоичного канала с независимыми ошибками. В таком канале появление предыдущей ошибки не влечет за собой появление последующей. В этой ситуации число R(i) ошибок кратности i в кодовой комбинации длиной n равно числу сочетаний C_nⁱ. =_c/K=K^-1_S=1^Lm_SP_S; (2.33). Поскольку ошибки независимы вероятность P(i) возникновения в кодовой комбинации ошибки кратности i равна P(i)=Pⁱ(1-P)^n-i (2.34), где Р-вероятность ошибки в канале. Учитывая, что в данном случае N_пр=S выражение (2.31) можно записать в виде I_K=-_i=0^SR(i)P(i)logP(i)-P_HlogP_H. Вторым слагаемым можно пренебречь поскольку, описываемая им функция не используется в процессе исправления ошибок. Поэтому с учетом (2.23 и 2.24) имеем I_K=-_i=0^SC_nⁱPⁱ(1-P)^n-i log₂[ Pⁱ(1-P)^n-i ] (2.35). Рассмотрим частный случай когда возникновение конкретной ошибки любой кратности и отсутствие ошибок имеют равную вероятность, т.е. Pⁱ(1-P)^n-i=P₁ при любом i. Величину Р₁ определим из условия нормировки _i=0^SC_nⁱP₁=1 (2.36), отражающего тот факт, что вероятность появления ошибки какой-либо кратности, включения и нулевую равна единице. Из (2.36) имеем P₁=(_i=0^SC_nⁱ)^-1 следовательно I_K=-_i=0^SC_nⁱP₁log₂P₁=log₂(_i=0^SC_nⁱ) (2.37). Поскольку под двоичной, то есть m=2 c учетом (2.37 и 2.38) имеем r_min=log₂(_i=0^SC_n). Найденное таким образом значение r_min совпадает с оценками полученными другим методами в частности с нижним пределом Хэмминга. Аналогичным образом могут быть найдены информационные пределы избыточности для других конфигураций ошибок в канале, например для пакетных ошибок, когда одиночные ошибки группируются в пакеты различной кратности. Полученные при этом результаты так же хорошо согласовывается с выводами полученными другими методами. Найденное таким образом значение r_min совпадает с оценками, полученными другими методами, в частности, с нижним пределом Хэмминга. Аналогичным образом могут быть найдены информационные пределы избыточности для других конфигураций ошибок в канале, например для пакетных ошибок, когда одиночные ошибки группируются в пакеты различной кратности. Получаемые при этом результаты также хорошо согласуются с выводами, полученными другими методами.

32 “ Общие принципы организации и математические модели систем управления техническими системами ”

Центральной концепцией теории систем, кибернетики, системного подхода, всей системологии является понятие системы. Формулировки определений системы выглядят просто как фиксация того или иного этапа процесса развития понятия системы. Цели, которые ставит перед собой человек, редко достижимы только за счет его собственных возможностей или внешних средств, имеющихся у него в данный момент. Такое стечение обстоятельств называется проблемной ситуацией. Другими словами, система есть средство достижения цели. Это определение выдвигает на первый план целевую подчиненность всех сторон организации системы. Однако даже на простых примерах обнаруживаются сложности: соответствие между целями и системами не всегда однозначно (одна система может быть связана с несколькими целями, одной цели могут отвечать разные системы) и не всегда очевидно (выявить действительные цели существующей системы непросто). Тем не менее целевая предназначенность системы - ее исходное, главное свойство. Те части системы, которые мы рассматриваем как неделимые, будем называть элементами. Части системы, состоящие более чем из одного элемента, назовем подсистемами. В результате получается модель состава системы, описывающая, из каких подсистем и элементов она состоит. Модель состава ограничивается снизу тем, что считается элементом, а сверху -границей системы. Как эта граница, так и границы разбиения на подсистемы определяются целями построения модели и, следовательно, не имеют абсолютного характера. Это не означает, что сама система или ее состав нереальны. Мы имеем дело не с разными системами, а с разными моделями системы. Системы, в которых происходят какие бы то ни было изменения со временем, будем называть динамическими, а модели, отображающие эти изменения, - динамическими моделями систем. Для разных объектов и систем разработано большое количество динамических моделей, описывающих процессы с различной степенью детальности: от самого общего понятия динамики, движения вообще, до формальных математических моделей конкретных процессов типа уравнений движения в механике или волновых уравнений в теории поля. Типы моделей прослеживаются при более глубокой формализации динамических моделей. При математическом моделирований некоторого процесса его конкретная реализация описывается в виде соответствия между элементами множества Х возможных "значений" х и элементов упорядоченного множества Т "моментов времени" t, т.е. в виде отображения Т Х: x(t) X^T, t Т. С помощью этих понятий можно строить математические модели систем. Необходимо строить математические модели систем, выход которых определяется не только значением входа в данный момент времени, но и теми значениями, которые были на входе в предыдущие моменты. Более того, в самой системе с течением времени как под влиянием входных воздействий, так и независимо от них могут происходить изменения, что также следует отразить в модели. В наиболее общей модели вводится понятие состояния системы как некоторой (внутренней) характеристики системы, значение которой в настоящий момент времени определяет текущее значение выходной величины. Состояние можно рассматривать как своего рода хранилище информации, необходимой для предсказания влияния настоящего на будущее. Обозначим это состояние через z(t). Все сказанное выше означает существование такого отображения : Z T Y, что y(t)=(t, z(t)), t Т. Явная зависимость  от t введена для учета возможности изменения зависимости выхода от состояния с течением времени. Это отображение называется отображением выхода. Для завершения построения модели нужно описать связь между входом и состоянием, т.е. ввести параметрическое семейство отображений _: Z X(•) Z, заданных для всех значений параметров tТ, T и t. Это означает принятие аксиомы о том, что состояние в любой момент t >  однозначно определяется состоянием z_ в момент  и отрезком реализации входа х(•) от  до t: z(t)=_ (z_, х(•))=(t; , z_, х(•)). Такое отображение называют переходным отображением. Итак, математическая модель системы - это задание множеств входов, состояний и выходов, и связей между ними: X |_Z |_Y. Конкретизируя множества X, Z и Y и отображения  и , можно перейти к моделям различных систем. Так, говорят о дискретных и непрерывных по времени системах в зависимости от того, дискретно или непрерывно множество Т. Далее, если множества X, Z и Y дискретной по времени системы имеют конечное число элементов, то такую систему называют конечным автоматом. Это довольно простой класс систем в том смысле, что для исследования конечных автоматов необходимы лишь методы логики и алгебры; в то же время это широкий и практически важный класс, так как в него входят все дискретные (цифровые) измерительные, управляющие и вычислительные устройства, в том числе и ЭВМ. Если X, Z и Y - линейные пространства, а  и  - линейные операторы, то и система называется линейной. Если к линейной системе дополнительно предъявить требования, состоящие в том, чтобы пространства имели топологическую структуру, а  и  были бы непрерывны в этой топологии, то мы приходим к гладким системам. Отображение процессов, происходящих в системе и в окружающей ее среде, осуществляется с помощью динамических моделей. Все указанные типы моделей являются формальными, относящимися к любым системам и, следовательно, не относящимися ни к одной конкретной системе. Чтобы получить модель заданной системы, нужно придать формальной модели конкретное содержание, т.е. решить, какие аспекты реальной системы включать как элементы модели избранного типа, а какие - нет, считая их несущественными. Этот процесс, обычно неформализуем, поскольку признаки существенности или несущественности в очень редком случае удается формализовать (к таким случаям относится, например, возможность принять в качестве признака существенности частоту встречаемости данного элемента в различных подобных, т. е. одинаково классифицируемых, системах). Столь же слабо формализованными являются признаки элементарности и признаки разграничения между подсистемами. В силу указанных причин, процесс построения содержательных моделей является процессом интеллектуальным, творческим. Тем не менее интуиции эксперта, разрабатывающего содержательную модель, немало помогают формальная модель и рекомендации по ее наполнению конкретным содержанием. Модель - это материальный или мысленно представляемый объект или процесс, который в процессе извлечения информации замещает оригинал, сохраняя его основные свойства. Математическая модель - это формализованная схема описания явления, объекта или процесса, выраженного на математическом языке и отражающая его основные свойства. Создание мат. модели делится на три этапа: Выбор параметров задачи (переменные, неизвестные), выбор которых однозначно определяет моделируемую задачу; Запись математической модели, т.е. запись условий задачи в виде математических соотношений; Постановка цели на сформулированные модели.

33 “Понятие модели. Виды моделей”

Модель - это материальный или мысленно представляемый объект или процесс, который в процессе извлечения информации замещает оригинал, сохраняя его основные свойства. Типы моделей: физические, математические, имитационные. Физические модели - это материальные объекты, представляющие копию изучаемого объекта или явления. Математическая модель - это формализованная схема описания явления, объекта или процесса, выраженного на математическом языке и отражающая его основные свойства. Создание мат. модели делится на три этапа: Выбор параметров задачи (переменные, неизвестные), выбор которых однозначно определяет моделируемую задачу; Запись математической модели, т.е. запись условий задачи в виде математических соотношений; Постановка цели на сформулированные модели. Статистические модели используются для описания явлений, которым не хватает информации для построения математических моделей. Данные модели широко используются для описания социальных, экономических, экологических и других явлений. Недостатком статистических моделей является опасность некорректного заключения о поведении системы вне диапазона значений используемых параметров. Положительным же свойством применения статистических моделей является возможность построения картины поведения модели на основе статистических данных, не обладая достаточным набором знаний для описания модели аналитически. Имитационная модель - программа, при выполнении которой на ЭВМ в численном виде воспроизводится процесс функционирования системы в соответствии с известным причинно-следственным механизмом, определяющим состояния элементов системы в очередные моменты времени через их состояния в прошлом. Первоначально моделью называли некое вспомогательное средство, объект, который в определенной ситуации заменял другой объект. При этом далеко не сразу была понята универсальность законов природы, всеобщность моделирования, т.е. не просто возможность, но и необходимость представлять любые наши знания в виде моделей. Осмысливание основных особенностей моделей привело к разработке многочисленных определений, типичным примером которых служит следующее: моделью называется некий объект-заместитель, который в определенных условиях может заменять объект-оригинал, воспроизводя интересующие нас свойства и характеристики оригинала, причем имеет существенные преимущества удобства (наглядность, обозримость, доступность испытаний, легкость оперирования с ним и пр.). Затем были осознаны модельные свойства чертежей, рисунков, карт - реальных объектов искусственного происхождения, воплощающих абстракцию довольно высокого уровня. Следующий шаг заключался в признании того, что моделями могут служить не только реальные объекты, но и абстрактные, идеальные построения. Типичным примером служат математические модели. В результате деятельности математиков, логиков и философов, занимавшихся исследованием оснований математики, была создана теория моделей. В ней модель определяется как результат отображения одной абстрактной математической структуры на другую, тоже абстрактную, либо как результат интерпретации структуры в терминах и образах второй. Сначала в сфере научных дисциплин информационного, кибернетического, системного направления, а затем и в других областях науки модель стала осознаваться как нечто универсальное, хотя и реализуемое различными способами. Модель есть способ существования знаний. Поскольку модели играют чрезвычайно важную роль в организации любой деятельности человека, все виды деятельности удобно разделить по направленности основных потоков информации, циркулирующих между субъектом и окружающим его миром. Разделим модели на познавательные и прагматические, что соответствует делению целей на теоретические и практические. Познавательные модели являются формой организации и представления знаний, средством соединения новых знаний с имеющимися. Поэтому при обнаружении расхождения между моделью и реальностью встает задача устранения этого расхождения с помощью изменения модели. Познавательная деятельность ориентирована в основном на приближение модели к реальности, которую модель отображает. Прагматические модели являются средством управления, средством организации практических действий, способом представления образцово правильных действий или их результата, т.е. являются рабочим представлением целей. Поэтому использование прагматических моделей состоит в том, чтобы при обнаружении расхождений между моделью и реальностью направить усилия на изменение реальности так, чтобы приблизить реальность к модели Основное различие между познавательными и прагматическими моделями можно выразить так: познавательные модели отражают существующее, а прагматические - не существующее, но желаемое и (возможно) осуществимое.Другим принципом классификации целей моделирования, может служить деление моделей на статические и динамические. Для одних целей нам может понадобиться модель конкретного состояния объекта, своего рода "моментальная фотография" интересующего нас объекта. Такие модели называются статическими. Примером являются структурные модели систем. В тех же случаях, когда наши цели связаны не с одним состоянием, а с различием между состояниями, возникает необходимость в отображении процесса изменений состояния. Такие модели называются динамическими; примером их служат функциональные модели систем. Модели делятся на абстрактные (идеальные) и материальные (реальные, вещественные). Абстрактные модели являются идеальными конструкциями, построенными средствами мышления, сознания. С моделями условного подобия приходится иметь дело очень часто, поскольку они являются способом материального воплощения абстрактных моделей, вещественной формой, в которой абстрактные модели могут передаваться от одного человека к другому, храниться до (иногда очень отдаленного) момента их использования, т.е. отчуждаться от сознания и все-таки сохранять возможность возвращения в абстрактную форму. Это достигается с помощью соглашения о том, какое состояние реального объекта ставится в соответствие данному элементу абстрактной модели. Такое соглашение принимает вид совокупности правил построения моделей условного подобия и правил пользования ими. Для того чтобы модель отвечала своему назначению, недостаточно взять готовую модель или создать новую; необходимо, чтобы существовали условия, обеспечивающие ее функционирование. Отсутствие (или недостаточность) таких условий лишает модель ее модельных свойств, т.е. переводит модель в качественно иное состояние нераскрытости ее потенциальных возможностей. Понятие модели относится не просто к объекту, который мы так называем; оно включает (в определенных отношениях): субъекта, организующего моделирование, и задачу, ради которой проводится моделирование (обоих - через цель); объект-оригинал, который моделируется; средства, из которых создается модель; и среду, в которой модель должна функционировать. Определение модели, то оно может выглядеть так: Модель есть отображение: целевое; абстрактное или реальное, статическое или динамическое; ингерентное; конечное, упрощенное, приближенное;имеющее наряду с безусловно-истинным условно-истинное и ложное содержание; проявляющееся и развивающееся в процессе его создания и практического использования.Его вполне можно заменить кратким эквивалентом: модель есть системное отображение оригинала.