Кодирования
3.3.5. Сверточные коды
Все рассмотренные ранее помехоустойчивые коды относились к блоковым кодам. Отличительной особенностью блоковых кодов является то, что закодированная последовательность символов представляет собой последовательность кодовых комбинаций (блоков) одинаковой длины n, каждая из которых кодировалась независимо от других. Иначе обстоит дело при использовании сверточных кодов. Дополнительные символы в таких кодах зависят от ряда предшествующих информационных символов, в результате чего передаваемая последовательность становится одним полубесконечным кодовым словом. Построение сверточных кодов лучше всего рассмотреть на примере работы кодера, который любым k0 символам входной информационной последовательности ставит во взаимно однозначное соответствие n0 символов выходной последовательности. Простейший сверточный кодер (рис. 3.16) представляет собой регистр сдвига с k0 разрядами, в котором символы кодовой последовательности формируются суммированием по модулю два значений с выходов некоторых разрядов регистра.
Рис. 3.16 Сверточные кодеры (и коды) характеризуются скоростью кодирования R=k0/n0, означающей, что если в каждый момент времени (такт) k0 символов входного кода поступают в регистр, то за это же время с выхода снимается n0 символов выходного кода. Для данного примера R=k0/n0 = 1/2, т.е. поступление каждого символа на вход приводит к появлению двух символов на выходе. Другой важнейшей характеристикой является длина кодового ограничения или простокодовое ограничение, равное числу разрядов регистра, в связи с чем эту характеристику называют иногда памятью кода. Величина nA = m´n0 называется полной длиной кодового ограничения. Величина полного кодового ограничения характеризует протяженность корреляционных связей в кодированной последовательности для одного информационного символа. Если на вход кодера подавать различные информационные последовательности и каждый раз на длине nA выходной последовательности фиксировать ее вес, то минимальный зафиксированный вес даст значение т.н. свободного кодового расстояния dСВ. Связи между разрядами регистра и сумматорами по модулю два удобно описывать порождающими полиномами. Для приведенной схемы Рассматриваемый сверточный кодер под воздействием нулевой входной последовательности будет выдавать нулевую выходную последовательность. Если, например, подать в кодер один символ 1, за которой последуют нули, то выходная последовательность будет иметь вид
Таким образом, входная последовательность 1000... порождает выходную последовательность 1101110000.... Порождающая матрица кода может быть построена аналогично ранее рассмотренным, но в виде полубесконечной матрицы
Выходная последовательность, соответствующая произвольной входной последовательности может быть получена путем суммирования по модулю два соответствующих сочетаний строк этой матрицы. Таким образом, сверточный код, формируемый этим кодером, имеет следующие параметры: -скорость кодирования R=1/2; -кодовое ограничение m=3; -полное кодовое ограничение nA=6; -свободное кодовое расстояние dСВ=5. Другой способ описания связей между входной и выходной последовательностями сверточного кодера состоит в использовании кодового дерева, в котором каждая вершина соответствует очередному входному символу, а на ребре, ведущем к этой вершине, записывается соответствующая совокупность входных символов. Таким образом, каждая входная последовательность задает некоторый путь на дереве, а совокупности символов, соответствующие ребрам, составляющим этот путь, образуют выходную последовательность. Ясно, что при росте длины входной последовательности число возможных путей растет экспоненциально, так что использование такого дерева не очень удобно. Более удобным является представление в виде т. н. решетчатого графа. Решетчатым называют граф, узлы которого находятся в узлах прямоугольной координатной сетки, т.е. образуют строки и столбцы. Граф полубесконечен справа, т.е. число столбцов полубесконечно. Число узлов в каждом столбце, т.е. число строк конечно и равно
Рис. 3.17
Продемонстрируем процесс кодирования с помощью решетчатого графа, например, кодируя входную комбинацию =101100..., т.е. выходная комбинация, найденная по графу (жирные линии) будет 1101001010, что можно проверить, воспользовавшись построенной ранее образующей матрицей и сложив по модулю два 1, 3 и 4 ее строки Задачу декодирования сверточного кода можно рассматривать как задачу нахождения пути на решетчатом графе с помощью некоторых правил декодирования. Как и в случае декодирования блоковых кодов по максимуму правдоподобия целесообразными оказываются попытки выбрать правильный путь, который лучше всего согласуется с принятой последовательностью, т.е. попытки минимизировать вероятность ошибки последовательности. Поскольку с ростом длины последовательности число путей растет экспоненциально, то на первый взгляд задача построения оценки последовательности по максимуму правдоподобия для сверточного кода кажется безнадежной. Однако, метод построения такой оценки достаточно легко найти, пытаясь непосредственно вычислить метрику для каждого пути на решетке. Вначале число путей действительно растет экспоненциально с ростом длины последовательности. Однако, вскоре появляется возможность исключить из рассмотрения такое число путей в каждой вершине, которое в точности уравновешивает число вновь появившихся путей. Таким образом, оказывается возможным иметь сравнительно небольшой список путей, который всегда будет содержать наиболее правдоподобный путь. Эта итеративная процедура декодирования называется алгоритмом Витерби. Проще всего рассмотреть функционирование алгоритма Витерби на примере уже приведенной решетчатой диаграммы для кода с R = 1/2 и m=3. Заметим, что в ней имеется ровно по два пути, ведущих в каждую вершину уровня 4. Поскольку, начиная с этого уровня, соответствующие пути совпадают, декодер максимального правдоподобия может без потери общности принимать решение соответствующее этой вершине. После того, как это сделано, аналогичная процедура может быть применена к следующему уровню и т.д. Именно таким образом работает алгоритм Витерби. Согласно ему на каждом уровне сравниваются два пути, входящие в каждую вершину, и сохраняется лишь тот из них, метрика которого лучше. В качестве метрики может служить расстояние Хэмминга между принятой последовательностью и кодовыми словами, считываемыми с ребер решетки. Другой путь с худшей метрикой исключается из рассмотрения. Оставшиеся пути называются выжившими. Для рассматриваемого кода с m=3 в каждый момент будет сохраняться не более 4 выживших путей. Для упрощения демонстрации работы алгоритма Витерби положим, что передавалась нулевая последовательность 00000000..., а принятой оказалась последовательность с одной ошибкой 10000000.... Тогда работа алгоритма может быть описана следующими фрагментами: 1) принимаемый кадр n0 символов – 10
Декодер выберет оба пути и определит метрику каждого из них – цифра над узлом. 2) принимаемый кадр 00
3) принимаемый кадр 00
4) принимаемый кадр 00
5) принимаемый кадр 00
6) принимаемый кадр 00
Можно заметить, что 5 и 6 кадры аналогичны, т.е. процесс будет повторяться при приеме каждого очередного кадра, поскольку больше ошибок в принятой комбинации нет. Можно также заметить, что метрика нулевого пути лучше всех остальных. Из примера ясно, что выживающие пути могут отличаться друг от друга в течение долгого времени. Однако в данном примере при приеме 6 кадра первые 4 ребра всех путей совпадают. В этот момент согласно алгоритму Витерби принимается решение о переданных символах, т.к. выжившие пути приходят из одной вершины, т.е. соответствуют оному информационному символу, т.е. по 6 кадру можно с максимальным правдоподобием предположить, что передавалась последовательность 00000000, соответствующая декодированной последовательности 0000. Глубина, на которой осуществляется принятие решения, не может быть вычислена заранее, она является случайной величиной, зависящей от серьезности происходящих в канале ошибок. Поэтому при практической реализации декодера Витерби устанавливается фиксированная глубина декодирования или ширина окна декодирования b. Каждый раз при приеме нового кадра декодер выдает выходящий за пределы окна самый старый символ одного из выживших путей. Такой процесс декодирования кадров продолжается бесконечно. Если b выбрано достаточно большим, то почти всегда при декодировании может быть принято однозначное решение. Если для данного канала с известными параметрами помех код выбран надлежащим образом, то это решение с большой вероятностью будет правильным. Этому, однако, может помешать несколько обстоятельств. Не все выжившие пути могут проходить через один и тот же узел. Возникает неопределенность, и процесс декодирования нарушается. Декодер может разрешить неопределенность, используя любое произвольное правило. Другая возможность состоит в том, что декодер не принимает решения, а отмечает этот участок последовательности, как сегмент кодового слова, который невозможно исправить. В этом случае декодер становится неполным декодером. Иногда декодер принимает однозначное, но ошибочное решение. Оно обязательно сопровождается последующими дополнительными ошибочными решениями, но декодер через некоторое время обнаружит это. Основные трудности при реализации алгоритма Витерби возникают из-за того, что сложность декодера экспоненциально растет с ростом длины кодового ограничения m. Поэтому значения m должны быть сравнительно небольшими m <10 или должны использоваться другие алгоритмы декодирования. Для того, чтобы ослабить влияние больших длин кодового ограничения, была разработана стратегия декодирования, игнорирующая маловероятные пути по решетке, как только они становятся маловероятными. Все такие стратегии поиска наиболее вероятного пути на решетке известны по общим названием последовательного декодирования. В отличие от декодера Витерби, который производит продолжение и обновление метрики всех путей, которые могут оказаться наилучшими, последовательный декодер в каждый момент времени продолжает лишь один путь, который имеет вид наиболее вероятного. На каждом уровне последовательный декодер находится в одном узле, смотрит на следующий кадр и выбирает ребро, ближайшее к принятому кадру, переходя по этому ребру в узел на следующем уровне. Если нет ошибок, процедура работает отлично, однако при наличии ошибок декодер может выбрать неправильный путь. Если декодер продолжает следовать по ложному пути, он обнаруживает, что происходит слишком много ошибок. Но это ошибки декодера, а не канала. Последовательный декодер вернется назад на несколько кадров и начнет исследовать альтернативные пути до тех пор, пока не найдется правдоподобный путь, затем он будет следовать вдоль этого альтернативного пути. Разработаны различные подробные алгоритмы реализации этих процедур. Наиболее популярным из них является алгоритм Фано. В этом алгоритме требуется знать вероятность p появления ошибочного символа в канале. Пока декодер следует по правильному пути вероятное число ошибок в первых l кадрах приблизительно равно p ln0. Декодер допускает несколько большее число ошибок, но если оно намного больше, то декодер сделает вывод о том, что он находится на ложном пути. Для декодера выбирается некоторый параметр p1, такой, что p<p1<1/2 и определяется т.н. перекошенное расстояние Таким образом, каждый раз, когда декодер, двигаясь вперед, посещает ранее исследованный узел, он имеет меньший порог. Декодер никогда не посетит один и тот же узел дважды с одним и тем же порогом. Следовательно, он может посещать любой узел конечное число раз. Это поведение гарантирует декодер от зацикливания. Декодер продолжает обработку данных, проводя правильное или неправильное декодирование. Основная сложность при реализации последовательного декодера состоит в том, что число вычислительных операций, необходимых для продвижения в следующую вершину кодового дерева, является случайной величиной. Наиболее существенным следствием непостоянства объема вычислений, требуемых для декодирования одного символа, является необходимость в наличии большой емкости памяти для буферизации поступающих и обрабатываемых данных. Использование в последовательном декодере буферной памяти любого, но конечного объема, приводит к ненулевой вероятности его переполнения. Исходя их этой характеристики, находится т.н. вычислительная скорость декодера R0. Если скорость кода R>R0, то в любом последовательном декодере будут возникать серьезные вычислительные трудности, связанные с частыми переполнениями буфера. Для декодирования сверточных кодов могут использоваться и методы синдромного декодирования, среди которых наиболее часто употребляемыми являются метод порогового декодирования и метод табличного поиска. Следует отметить, что синдромное декодирование в преобладающем большинстве случаев используется только для систематических сверточных кодов, т.е. таких, у которых кодовая последовательность содержит явно выделяемые информационные и контрольные символы. Пороговое декодирование сверточных кодов основано на тех же принципах, что и мажоритарное декодирование блоковых кодов. Декодер, реализующий этот алгоритм, по принятой информационной последовательности вычислят проверочные символы. Для этого декодер содержит копию кодера. Далее полученные с помощью этой копии проверочные символы складываются по модулю два с принимаемой проверочной последовательностью, в результате чего формируется синдромная последовательность, записываемая в регистр сдвига. С помощью линейного преобразования синдрома формируется система ортогональных проверок. Если результаты этих проверок подать на входы пороговой или решающей схемы, то на ее выходе будет формироваться оценка ошибочного символа. Суммируя его по модулю два с соответствующим информационным символом, который хранится в копии кодера, можно исправить ошибку. При этом выходной символ пороговой схемы по цепи обратной связи подается еще и на схему вычисления синдрома и корректирует его, устраняя влияние вычисленной ошибки на последующие символы. Такая процедура порогового декодирования называется декодированием с обратной связью. Среди сверточных кодов, допускающих пороговое декодирование, самыми простыми являются т.н. самоортогональные коды. Декодирование самоортогональных кодов осуществляется крайне просто. Это связано с тем, что при декодировании нет необходимости проводить линейное преобразование символов синдрома для получения ортогональных проверок, поскольку в качестве таковых используются непосредственно символы синдрома. Еще одним классом сверточных кодов, допускающих пороговое декодирование, являются ортогонализируемые коды. Ортогонализируемый код – это код, который допускает для каждого информационного символа построение системы ортогональных проверок, являющихся линейными комбинациями символов синдрома. Параметры этих кодов можно найти там же. Если шумы в канале не выходят за пределы допустимых, то исправление ошибок осуществляется правильно. Если шумы превышают корректирующие способности кода, то могут возникнуть естественные ошибки декодирования. Однако, поскольку декодер содержит цепь обратной связи, то при возникновении ошибки декодирования по неправильной оценке значений ошибок осуществляется неправильная коррекция синдрома, что может привести к новой ошибке декодирования. Это явление характерно для сверточных кодов и известно под названием распространения ошибок. Одним из методов борьбы с распространением ошибок является т.н. метод дефинитного декодирования. При этом декодировании исправления синдрома не производится, т.е. обратная связь отсутствует. Однако при таком декодировании и достаточно больших кодовых ограничениях корректирующие способности кодов обычно оказываются хуже, чем при декодировании с обратной связью. Отличие метода табличного поиска от метода порогового декодирования с обратной связью состоит только в том, что в качестве решающего устройства используется ПЗУ с произвольным доступом, из которого по адресу, равному текущему синдрому, выбирается наиболее вероятная комбинация ошибок, записанная в него на этапе проектирования системы.
3.3.6. Каскадные коды
Каскадные коды были введены в качестве метода практической реализации кодов с очень большой длиной блока и весьма высокой корректирующей способностью. Эти цели достигаются при наличии нескольких уровней кодирования многими различными способами. Распространенной является схема с двумя уровнями кодирования (рис. 3.18).
Рис. 3.18 Совокупность внутреннего кодера, канала и внутреннего декодера называется суперканалом. Совокупность внешнего и внутреннего кодеров называется суперкодером, а соответствующая совокупность на приемной стороне – супердекодером. Длина кодовой комбинации каскадного кода N*=nN, количество информационных символов в ней K*=kK, а скорость кода определяется по известной формуле Наиболее часто в качестве внешнего кода используются коды Рида – Соломона, поскольку они являются кодами с максимальным расстоянием d=n-k+1 и относительно просто реализуются. В качестве внутреннего кода может использоваться например (2K-1, K)-код максимальной длины. Однако эти коды могут быть полезны только при использовании в очень широкополосных каналах, т.е. когда требуемые скорости передачи намного меньше той, которую обеспечивает полоса частот канала, поскольку эти коды обладают очень низкой скоростью. Для получения скоростей передачи в диапазоне
3.3.7. Оценка эффективности применения корректирующих кодов
Обычно качество системы связи оценивается отношением (Eб/N0) энергии Eб, приходящейся на один информационный символ (бит) к спектральной мощности N0 шума в канале, которое требуется обеспечить для достижения заданной вероятности ошибки pб (т.е. верности передачи). Термин «выигрыш от кодирования» указывает на улучшение характеристик системы от использования данной схемы кодирования. Представление о взаимосвязи этих характеристик дают графики зависимостей pб =f(Eб/N0). Обычный метод определения выигрыша от кодирования состоит в сравнении графиков pб =f(Eб/N0) для систем без кодирования и с кодированием и определении разности значений Eб/N0 при данной вероятности ошибки Например, в системе без кодирования для получения вероятности ошибки на бит на выходе фазового демодулятора, не больше pб =10-5 необходимо обеспечить Eб/N0 = 9,6 дБ (рис. 3.19).
Рис. 3.19
В этой же системе, но при использовании циклического кода с n=255 и RK=0,8 та же верность, т.е. pб =10-5 может быть достигнута при Eб/N0 = 6,3 дБ. В этом случае энергетический выигрыш от кодирования составляет 3,3 дБ. Меняя для данного типа кода параметры кода, можно построить семейство таких характеристик. Семейства зависимостей pб =f(Eб/N0) для различных кодов можно найти в справочной литературе. По этим кривым можно оценить энергетический выигрыш от кодирования, который учитывает как возможность снижения отношения сигнал/шум за счет уменьшения уровня сигнала, обеспечиваемую исправлением ошибок в декодере, так и дополнительные затраты энергии на передачу кодовых комбинаций, вызванные введением избыточности. Методы исправления ошибок получили широкое распространение в каналах с аддитивным гауссовским шумом. Типичные случаи применения – радиолинии прямой видимости, в том числе линии космической и спутниковой связи. В подобных случаях цель состоит в уменьшении требуемого значения Eб/N0 при фиксированной вероятности ошибки по сравнению с этим значением в системе без кодирования. Выигрыш от кодирования может быть затем использован наиболее эффективным способом: можно, например, уменьшить размер антенн или увеличить скорость передачи. Для получения значительного выигрыша от кодирования в таких каналах наиболее пригодны сверточные коды с малой длиной кодового ограничения и с декодированием Витерби. В частности, сверточный код с R =1/2 и полной длиной кодового ограничения равной 6 при pб =10-5 дает энергетический выигрыш 5 дБ. При фиксированном уровне сложности такой подход обычно предпочтительнее блоковых кодов. При умеренных и высоких скоростях поступления данных (от 10 кбит/c до 20 Мбит/с) сложность реализации данного подхода существенно меньше, чем других методов, приводящих к сравнимому выигрышу от кодирования. Если будут созданы более эффективные алгоритмы декодирования блоковых кодов, они, несомненно, будут сравнимы с алгоритмом Витерби. Пока что сложность существенно уменьшается лишь при использовании очень простого порогового декодирования и декодирования с табличным поиском. Однако получаемый при этом выигрыш от кодирования уменьшается на несколько децибел. При очень высоких скоростях поступления данных (свыше 20 Мбит/с) система, в которой каскадируются коды Рида-Соломона и короткие блоковые коды, при меньшей сложности дает примерно тот же выигрыш от кодирования, что и декодер Витерби. Для очень высоких скоростей поступления данных в некоторых системах использовались параллельные декодеры Витерби. Однако такая система оказалась очень дорогой. Алгоритм Витерби при высоких скоростях поступления данных является одним из лучших по зависимости стоимости от сложности. Сложность методов, которые могут оказаться лучше декодирования Витерби, пропорциональна скорости поступления данных. Оказывается, что они становятся привлекательными лишь при умеренных скоростях поступления данных (до 1 Мбит/с). При таких скоростях каскадная система в которой применяется код Рида-Соломона и декодер Витерби, дает примерно на 2 децибела больший выигрыш, чем обычный декодер Витерби, однако сложность при этом удваивается или утраивается. Несколько лучшим оказывается использование последовательного декодирования. При скоростях поступления данных до нескольких сотен килобит в секунду этот метод обеспечивает лучшие характеристики, чем декодирование Витерби, при примерно той же сложности. При более низких скоростях преимущества последовательного декодирования возрастают. При очень малой вероятности ошибки (pб =10-8) дополнительные преимущества приобретают коды с большим кодовым расстоянием. Например, каскадная система с последовательным декодированием приводит к выигрышу от кодирования, превышающему выигрыш, получаемый при декодировании Витерби, на 1 децибел. Таким образом, при очень низких вероятностях ошибки эти методы требуют дополнительного внимания. Все приведенные до сих пор оценки характеристик относились к каналам без памяти, т.е. к каналам, в которых вероятность ошибки не зависит от времени. В случаях, когда нужно учитывать пакеты ошибок, возможные решения состоят в применении таких циклических кодов, какими являются коды Файра, или каких-либо кодера и декодера, предназначенных для исправления случайных ошибок (а не пакетов), вместе с парой устройств, состоящей из устройства перемежения и устройства восстановления после перемежения (рис. 3.20).
Рис. 3.20 При таком подходе последовательность на выходе кодера подвергается перемежению до передачи по каналу и восстанавливается перед декодированием, так что на входе декодера ошибки распределяются более равномерно (не пакетируются). Устройство перемежения переупорядочивает (переставляет) символы в последовательности некоторым детерминированным образом. С устройством перемежения связано устройство восстановления после перемежения, с помощью которого осуществляется обратная перестановка и восстанавливается исходный порядок символов. Существует много типов таких устройств. Два важных класса устройств перемежения – это периодические и псевдослучайные устройства перемежения. Периодическим называют такое устройство перемежения, в котором перестановка является периодической функцией времени. Среди периодических устройств перемежения можно выделить два основных типа – блоковые устройства перемежения и сверточные устройства перемежения. На вход блоковых устройств перемежения символы поступают блоками, и устройство производит одну и ту же перестановку каждого блока символов. Сверточные устройства перемежения не имеют фиксированной блочной структуры, они осуществляют периодическую перестановку полубесконечной последовательности кодовых символов. Различие между устройствами перемежения этих двух типов очень похоже на различие между блоковыми и сверточными кодами. Псевдослучайное устройство перемежения представляет собой блоковое устройство, которое берет блоки из определенного количества символов и переставляет из псевдослучайным образом. Это можно сделать, записав символы блока последовательно в ОЗУ устройства перемежения, а затем считав их псевдослучайным образом. Требуемую перестановку можно записать в ПЗУ, содержимое которого использовать для адресации ОЗУ устройства перемежения. Такой метод обеспечивает высокую степень устойчивости при изменении параметров пакетов ошибок, однако его сложность превышает сложность блокового или сверточного устройства перемежения того же объема. Наиболее интересным является применение таких устройств для защиты от организованных помех. Из анализа семейств характеристик pб =f(Eб/N0) построенных для различных кодов при различных длинах пакетов и их интенсивностях следует, что при малых длинах пакетов или их малой интенсивности применение перемежения не приносит ощутимых результатов. Так, для упомянутого ранее сверточного кода с R=1/2 и полной длиной кодового ограничения равной 6 использование перемежения не оправдано, если длины пакетов не превышают пяти. И наоборот, ухудшение характеристик, вызываемое случайными пакетами ошибок, показывает, что перемежение необходимо во всех случаях, кроме случая, когда длина пакета или их интенсивность очень мала. Таким образом, применение корректирующих кодов позволяет повысить верность передачи, т.е. уменьшить вероятность ошибки, либо при заданной верности повысить энергетическую эффективность системы снижением отношения сигнал/шум за счет уменьшения уровня сигнала. Многообразие кодов и методов декодирования делает почти невозможным составление полного каталога на все потенциально возможные случаи. Поэтому окончательное решение о целесообразности применения того или иного корректирующего кода с тем или иным методом декодирования можно принять лишь после сравнения показателей эффективности системы с кодированием и без него, с кодированием тем или иным классом кодов, с использованием того или иного метода декодирования. Техническая эффективность системы передачи информации определяется количеством и качеством информации, переданной за некоторый промежуток или в единицу времени, т.е. скоростью передачи R (бит/с) и верностью передачи или вероятностью ошибки p. Для обеспечения требуемых R и p используется канал с полосой F и отношением сигнал/шум Q, которые являются основными ресурсами канала. Целесообразно ввести коэффициенты эффективности, определяющие энергетическую b и частотную g эффективность системы передачи:
Эти коэффициенты имеют физический смысл удельных скоростей передачи, приходящихся на единицу отношения сигнал/шум и на единицу полосы пропускания канала соответственно. В качестве обобщенного показателя технической эффективности системы передачи вводится коэффициент использования пропускной способности канала или информационная эффективность
где С – пропускная способность канала. С учетом формулы Шеннона (2.29) и выражений (3.36) и (3.37) можно выразить информационную эффективность через частотную и энергетическую
Если принять эту функцию в качестве целевой, можно определить ее максимальное значение из следующих соображений. Согласно теореме Шеннона при соответствующих способах передачи (кодирования и модуляции) и приема (декодирования и демодуляции) значение h может быть сколь угодно близким к единице при сколь угодно малой ошибке. Положив hmax=1, из (3.38) получим
Если (3.39) представить в виде кривой на плоскости
Рис. 3.21
Для реальных систем ошибка всегда имеет место и h<1. В этом случае можно отдельно определить b и g и построить кривые 1) максимизировать энергетическую эффективность b при допустимых изменениях g<g!, где g! - область допустимых изменений g, и заданной ошибке p< pдоп; 2) максимизировать частотную эффективность g при допустимых изменениях b < b !, где b ! - область допустимых изменений b, и заданной ошибке p< pдоп. Например, пусть заданы скорость передачи R, полоса частот канала F и отношение сигнал-шум Q. Тогда область возможных значений b и g можно разбить на четыре квадранта. Системы, расположенные в I квадранте, удовлетворяют требованиям по обоим показателям b > b* и g > g *. Системы, расположенные в квадранте II, удовлетворяют треб
|
и 
. При таком представлении символы на входе кодера могут быть получены путем умножения входной последовательности на порождающие полиномы, т.е. 
и 
. Рассматриваемый в примере сверточный код является несистематическим, поскольку ни 
, ни 
не совпадают с входной последовательностью 
. Для получения систематического сверточного кода необходимо было бы положить или 
, или 
, т.е. убрать один из сумматоров, чтобы информационная входная последовательность стала частью выходной.
.
, где m - длина кодового ограничения. Конфигурация ребер, соединяющих узлы каждого столбца с узлами столбца справа, одинакова для всего графа. На основании сказанного построим решетчатый граф (рис. 3.17) для кодера, приведенного ранее, условившись, что из двух ребер, выходящих из каждого узла, верхнее соответствует входному символу 0, нижнее – 1.
.
, где 
- расстояние Хэмминга между принятым словом и текущим путем по решетке. Для правильного пути 
, в связи с чем 
и возрастает по мере движения. До тех пор, пока 
возрастает, декодер продолжает движение вперед по решетке. Если 
. Каскадирование обеспечивает такую структуру кода, что декодирование может осуществляться с помощью двух декодеров для кодов с длинами N и n соответственно, что позволяет существенно снизить сложность декодера по сравнению с той, которая потребовалась бы при одном уровне кодирования при прочих равных условиях.
в качестве внутреннего кода может быть использован короткий блоковый код, обеспечивающий высокоскоростное декодирование. В качестве внутренних кодов применяются также сверточные коды с малой длиной кодового ограничения и декодированием Витерби. Эта структура каскадного кодирования является одной из самых эффективных и перспективных.
и 
(3.36)
(3.37)
. (3.38)
. (3.39)
, то получим т.н. границу Шеннона (рис. 3.21). Полученная кривая является предельной и отражает наилучший обмен между b и g. Следует заметить, что g -эффективность может изменяться в широких пределах: от 0 до µ при аналоговой передаче и от 0 до 2logm при дискретной передаче, в то время как b -эффективность ограничена сверху, поскольку при g®0 bmax=1/ln2 (1,6 дБ).
при p=const, которые будут расположены ниже границы Шеннона. Ход этих кривых зависит от вида модуляции, типа и параметров используемого кода и способов обработки сигнала. Полученные таким образом bg -диаграммы позволяют выбрать системы, удовлетворяющие заданным требованиям, т.е. осуществить оптимизацию по коэффициентам b и g. При этом можно осуществить оптимизацию по одной из частных стратегий:
