Устройство и способ для турбоперемежения

 

Изобретение относится к турбокодеру, используемому в системах радиосвязи, в цифровых сотовых системах, цифровых сетях с интеграцией служб. Технический результат заключается в улучшении реализации свободного расстояния турбокода для случая, при котором входное информационное слово имеет вес Хэмминга, равный 1, когда вводимое в перемежитель информационное слово имеет блоковый тип, а также создание перемежителя, в котором свободное расстояние уменьшается, когда входное информационное слово имеет вес Хэмминга, равный 1. В способе осуществляют разделение кадра входных К информационных битов на множество групп с последующим сохранением разделенных групп в памяти перемежения информационных битов групп и сдвиг информационного бита, находящегося в последней позиции последней группы, в позицию, предшествующую последней позиции, выбор групп в соответствии с заданным порядком выбора и выбор одного из информационных битов в выбранной группе. 7 с. и 9 з.п. ф-лы, 12 ил., 3 табл.

Область техники Настоящее изобретение относится в целом к турбокодеру, используемому в системах радиосвязи (в том числе спутниковых системах, цифровых сетях с интеграцией служб (ISDN), цифровых сотовых системах, широкополосных системах множественного доступа с кодовым разделением каналов (Ш-МДКР) и системах IMT-2000) и, в частности, к внутреннему перемежителю турбокодера.

Предшествующий уровень техники В общем случае перемежитель, используемый в турбокодере, рандомизирует адрес входного информационного слова и улучшает свойство расстояния кодового слова. В частности, было принято, что турбокод будет использоваться в дополнительном канале (или канале передачи данных) эфирных интерфейсов стандартов IMT-2000 (или в МДКР-2000) и IS-95C и в канале данных UMTS (универсальной системы мобильной связи), предложенной Европейским институтом стандартов связи (ETSI). Таким образом, требуется способ реализации перемежителя для этих целей. Кроме того, изобретение относится к коду исправления ошибок, который сильно влияет на улучшение работы существующих и перспективных цифровых систем связи.

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

Работа турбокодера зависит от его внутреннего перемежителя. В целом увеличение размера входного кадра (т.е. числа информационных битов, заключенных в одном кадре) увеличивает эффективность турбокодера. Однако увеличение размеров перемежителя вызывает возрастание вычислений в геометрической прогрессии. Поэтому в общем случае невозможно реализовать перемежитель для кадра большого размера.

Поэтому в общем случае перемежители реализуются путем определения условий, удовлетворяющих нескольким заданным критериям. Это следующие критерии.

Свойство расстояния: между смежными символами кодового слова должно поддерживаться определенное расстояние. Это то же самое, что свойство расстояния кодового слова сверточного кода, и в качестве такого критерия используется минимальное свободное расстояние, являющееся значением пути кодового слова или последовательности кодового слова с минимальным весом Хэмминга из последовательностей кодовых символов (или путей кодового слова) на решетке. В общем случае предпочтительно, чтобы перемежитель имел по возможности большее свободное расстояние.

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

Хотя вышеприведенные критерии применимы к обобщенному турбоперемежителю, сложно ясно анализировать эти свойства по мере увеличения размера перемежителя.

Кроме того, другая проблема, возникающая при проектировании турбоперемежителя, состоит в том, что минимальное свободное расстояние турбокода варьируется в соответствии с типом входного кодового слова. То есть, когда входное информационное слово имеет особую комбинацию последовательности, определяемую как критическая комбинация информационной последовательности (ККИП), свободное расстояние символов выходного кода, выработанных турбокодером, имеет очень малую величину. Если входное информационное слово имеет вес Хэмминга, равный 2, ККИП возникает, когда входное информационное слово имеет два информационных бита со значением "1", и может возникать также тогда, когда входное информационное слово имеет три или более информационных битов со значением "1". Однако в большинстве случаев, когда входное информационное слово имеет два информационных бита со значением "1", формируется минимальное свободное расстояние, и большинство ошибочных событий происходит в этом состоянии. Поэтому при проектировании турбоперемежителя обычно проводится анализ случая, при котором входное информационное слово имеет вес Хэмминга, равный 2. ККИП существует по той причине, что турбокодер обычно использует кодеры РССК (Рекурсивных Систематических Сверточных Кодов) в качестве компонентных кодеров, показанных на фиг.1 (описывается ниже). Для улучшения работы турбокодера, в качестве полинома обратной связи (gf(x) на фиг.1) должен использоваться примитивный полином из порождающих полиномов для компонентного кодера. Поэтому, если количество блоков памяти кодера РССК равно m, последовательность обратной связи, выработанная полиномом обратной связи, непрерывно повторяет одну и ту же комбинацию с периодом 2^m-1. Поэтому, если входное информационное слово "1" принято в момент, соответствующий этому периоду, над одинаковыми информационными битами производится операция "Исключающее ИЛИ", так что состояние кодера РССК вследствие этого становится полным нулем, тем самым в качестве выходных символов вырабатываются все нули. Это означает, что вес Хэмминга для кодового слова, выработанного кодером РССК, имеет после этого события постоянное значение. То есть, свободное расстояние турбокода сохраняется по прошествии этого времени, а ККИП становится главной причиной уменьшения свободного расстояния турбокодера, в то время как желательно большее свободное расстояние, как отмечено выше.

В этом случае (в известном турбоперемежителе) для увеличения свободного расстояния турбоперемежитель случайным образом рассредоточивает входное информационное слово ККИП для предотвращения уменьшения свободного расстояния в выходном символе другого компонентного кодера РССК.

Установленные выше свойства являются фундаментальными характеристиками известных турбоперемежителей. Тем не менее, для ККИП общепринято, чтобы информационное слово имело минимальный вес Хэмминга, если входное информационное слово имеет вес Хэмминга, равный 2. Другими словами, тот факт, что ККИП может быть выработана, даже если входное информационное слово имеет вес Хэмминга, равный 1 (т.е., если входное информационное слово имеет один информационный бит со значением "1"), игнорировалось, когда вводимое в турбокодер информационное слово имело вид блока, состоящего из кадров.

К примеру, первичный перемежитель (ПП), представляющий рабочую модель перемежителя турбокода, определенного нынешним стандартом UTMS, имеет эти проблемы, тем самым имея ухудшенное свойство свободного расстояния. То есть алгоритм реализации модели ПП турбоперемежителя содержит три стадии, вторая из которых, играющая наиболее важную роль, выполняет случайную перестановку информационных битов соответствующих групп.Эта вторая стадия разделена на три случая - Случай А, Случай Б и Случай В, причем Случай Б всегда включает тот случай, при котором свободное расстояние уменьшается из-за события, при котором входное информационное слово имеет вес Хэмминга, равный 1. Вдобавок, даже Случай В содержит возможность того, что такое событие произойдет. Подробно эти проблемы будут описаны ниже со ссылкой на ПП.

В заключение, когда необходимы различные размеры перемежителя, а сложность реализации аппаратного обеспечения ограничена в системе IMT-2000 или UMTS, турбоперемежитель должен быть сконструирован так, чтобы гарантировать оптимальную характеристику перемежителя, учитывая эти ограничения. То есть требуемый перемежитель должен обеспечить одинаковую характеристику для различных размеров перемежителя, удовлетворяя при этом установленным выше свойствам. Недавно было предложено несколько типов перемежителей для турбоперемежителя ПКСК (параллельных каскадных сверточных кодов), а турбоперемежитель ЛКП (линейной конгруэнтной последовательности) был условно определен в качестве турбоперемежителя в спецификациях стандартов IMT-2000 (или МДКР-2000) и IS-95C. Однако большинство таких турбоперемежителей имеет проблемы ККИП с весом Хэмминга, равным 1, а подробности воплощения этих турбоперемежителей до сих пор не определены. Поэтому настоящее изобретение предлагает решение проблем турбоперемежителя и новый способ реализации турбоперемежителя. Кроме того, изобретение представляет ПП-перемежитель, являющийся рабочим вариантом турбоперемежителя UMTS, и предлагает решение этой проблемы перемежителя.

Итак, известное из предшествующего уровня техники имеет следующие недостатки.

(1) Турбоперемежитель разработан для бесконечного размера кадра на основе ККИП, для которого входное информационное слово имеет вес Хэмминга, равный 2, без учета того факта, что определение ККИП на основании типа входного информационного слова ограничено размером кадра. Однако в реальной системе кадр имеет конечный размер, что вызывает уменьшение свободного расстояния турбокода.

(2) При разработке существующего турбоперемежителя не был учтен тот факт, что входное информационное слово может иметь вес Хэмминга, равный 1. Другими словами, для конечного размера кадра правило построения турбоперемежителя должно определяться с учетом того факта, что минимальное свободное расстояние, вырабатываемое в турбоперемежителе ПКСК, определяется ККИП с весом Хэмминга, равным 1. Однако для существующих турбоперемежителей это учитывалось не полностью.

(3) Первичный перемежитель (ПП), рассматриваемый как рабочее представление перемежителя турбокода, определенного спецификацией UMTS, имеет такие проблемы, а тем самым и ухудшенную характеристику свободного расстояния.

Сущность изобретения Следовательно, задачей настоящего изобретения является обеспечение перемежающего устройства и способа анализа свойств турбоперемежителя и свойства критической комбинации информационной последовательности (ККИП) для улучшения работы турбоперемежителя.

Еще одной задачей настоящего изобретения является обеспечение перемежающего устройства и способа улучшения реализации свободного расстояния турбокода для случая, при котором входное информационное слово имеет вес Хэмминга, равный 1, когда вводимое в перемежитель информационное слово имеет блоковый тип, состоящий из кадров.

Также задачей настоящего изобретения является создание перемежающего устройства и способа решения той проблемы, что свободное расстояние уменьшается, когда входное информационное слово имеет вес Хэмминга, равный 1, в первичном перемежителе (ПП), который является турбоперемежителем, описанным в спецификации UMTS.

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

Краткое описание чертежей Вышеупомянутые и прочие задачи, признаки и преимущества настоящего изобретения поясняются в последующем подробном описании, иллюстрируемом чертежами, на которых представлено следующее: Фиг.1 - схема, иллюстрирующая обобщенный параллельный турбокодер; Фиг.2 - схема, иллюстрирующая обобщенный перемежитель; Фиг.3 - схема, иллюстрирующая обобщенный обращенный перемежитель; Фиг. 4 - схема, иллюстрирующая способ генерирования критической комбинации информационной последовательности (ККИП) в турбоперемежителе; Фиг. 5 - схема, иллюстрирующая еще один способ генерирования ККИП в турбоперемежителе;
Фиг. 6 - схема, иллюстрирующая способ решения проблемы, возникающей при генерировании ККИП по фиг.4;
Фиг. 7 - схема, иллюстрирующая способ решения проблемы, возникающей при генерировании ККИП по фиг.5;
Фиг. 8 - схема, иллюстрирующая еще один способ решения проблемы, возникающей при генерировании ККИП в турбоперемежителе;
Фиг.9 - схема, иллюстрирующая способ генерирования ККИП в двумерном турбоперемежителе;
Фиг. 10 - схема, иллюстрирующая способ решения проблемы, возникающей при генерировании ККИП по фиг.7;
Фиг. 11 - функциональная схема, иллюстрирующая перемежающее устройство для подавления ККИП в соответствии с выполнением по настоящему изобретению;
Фиг. 12 - блок-схема алгоритма, объясняющая процесс перемежения модифицированного ПП (первичного перемежителя), соответствующего варианту выполнения настоящего изобретения.

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

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

Фиг.1 показывает структуру обобщенного параллельного турбокодера, который подробно раскрыт в патенте США 5446474, выданном 29 августа 1995, который включен сюда посредством ссылки.

Согласно фиг.1 турбокодер содержит первый компонентный кодер 111 для кодирования данных входного кадра, перемежитель 112 для перемежения данных входного кадра и второй компонентный кодер 113 для кодирования выхода перемежителя 112. Известный кодер РССК (рекурсивных систематических сверточных кодов) обычно используется в качестве первого и второго компонентных кодеров 111 и 113. Ниже первый компонентный РССК-кодер 111 будет обозначаться как РССК1, а второй компонентный РССК-кодер 113 будет обозначаться как РССК2. Далее, перемежитель 112 имеет тот же размер, что и кадр входного бита информации, и перестраивает последовательность битов информации, подаваемых во второй компонентный кодер 113 для уменьшения корреляции между этими битами информации.

Фиг. 2 и 3 показывают основные структуры обобщенного перемежителя и обращенного перемежителя соответственно.

Со ссылками на фиг.2 ниже описан перемежитель для перемеженного вывода данных кадра из первого компонентного кодера. Адресный генератор 211 вырабатывает адрес считывания для изменения последовательности входных битов данных в соответствии с размером L данных входного кадра и входным таймером и снабжает память 212 перемежителя выработанным адресом считывания. Память 212 перемежителя последовательно сохраняет входные данные в режиме записи и выводит сохраненные данные в соответствии с адресом считывания, обеспечиваемым адресным генератором 211, в режиме чтения. Счетчик 213 ведет отсчет входного таймера и подает значение таймера в память 212 перемежителя в качестве адреса записи. Как описано выше, перемежитель последовательно сохраняет входные данные в памяти 212 перемежителя в режиме записи и выводит данные, сохраненные в памяти 212 перемежителя, в соответствии с адресом считывания, подаваемым из адресного генератора 211 в режиме чтения. Альтернативно возможно также изменять последовательность входных битов данных перед их сохранением в памяти перемежителя в режиме записи, а затем считывать сохраненные данные в режиме чтения.

Со ссылками на фиг.3 описан обращенный перемежитель. Адресный генератор 311 вырабатывает адрес записи для восстановления последовательности входных битов данных в начальную последовательность в соответствии с размером L данных входного кадра и входным таймером и снабжает память 312 обращенного перемежителя выработанным адресом записи. Память 312 обращенного перемежителя сохраняет входные данные в соответствии с адресом записи, подаваемым из адресного генератора 311, в режиме записи, а затем выводит сохраненные данные в режиме чтения. Счетчик 313 ведет отсчет входного таймера и подает значение таймера в память 312 обращенного перемежителя в качестве адреса считывания. Как описано выше, обращенный перемежитель имеет ту же структуру, что и перемежитель, но его действие обратно действию перемежителя. Обращенный перемежитель отличается от перемежителя главным образом тем, что входные данные имеют различные последовательности как в режиме считывания, так и в режиме записи. Поэтому для удобства ниже приводится только описание перемежителя.

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

Для улучшения характеристики турбокодера может использоваться примитивный полином в качестве полинома обратной связи из порождающего полинома для компонентного кодера. Полином обратной связи задается путем задания отводов для обратной связи в компонентных РССК-кодерах 111, 113 по фиг.1 в полиноме, а полином обратной связи определяется как gf(x).

Если рассматривать фиг.1, gf(x)=1+х²+х³. То есть наивысший порядок показывает глубину памяти, а самое правое слагаемое определяет, является ли коэффициент ³ в gf(x) нулем или единицей. Следовательно, если количество блоков памяти РССК-кодера равно m, последовательность обратной связи, выработанная полиномом обратной связи, постоянно повторяет одну и ту же комбинацию с периодом 2^m-1. Таким образом, если входное информационное слово "1" принимается в момент, соответствующий этому периоду (например, для m=3, если принято информационное слово "10000001..."), над одинаковыми информационными битами производится операция "Исключающее ИЛИ", так что состояние РССК-кодера вследствие этого становится полностью нулевым, тем самым генерируя в качестве выходных символов все нули. Это означает, что вес Хэмминга кодового слова, выработанного РССК-кодером, имеет после этого события постоянное значение "1". То есть это значит, что свободное расстояние турбокода после этого сохраняется, а ККИП становится главной причиной уменьшения свободного расстояния турбокодера.

В этом случае для увеличения свободного расстояния турбоперемежитель случайным образом рассредоточивает входное информационное слово ККИП для предотвращения уменьшения свободного расстояния в выходном символе другого компонентного РССК-кодера. Приведенная в конце описания Таблица 1 показывает последовательность обратной связи, выработанную из gf(x)=1+х²+-х³. В Таблице 1 X(t) обозначает входной информационный бит в момент t входного информационного слова; m(t), m(t-1) и m(t-2) обозначают три состояния памяти РССК-кодера соответственно. Поскольку количество блоков памяти равно 3, период равен 2³-1=7.

Из Таблицы 1 следует, что если X(t)=1 в момент t=7, то m(t), m(t-1) и m(t-2) вследствие этого все становятся нулевыми состояниями. Следовательно, вес Хэмминга следующих выходных символов всегда становится равным нулю. В этом случае, если турбоперемежитель снабжает РССК2 входной информационной последовательностью "10000001000. . . ", как это и происходит, вес Хэмминга выходных символов в последующий момент t=7 не изменится после этого и в РССК2, использующем тот же полином обратной связи, по той же причине. Это вызывает уменьшение свободного расстояния всех выходных символов турбокодера. Для того, чтобы предотвратить это, турбоперемежитель изменяет начальную входную информационную последовательность "10000001000..." во входную информационную последовательность с другой структурой (например, изменяет положение информационного бита "1" так: 110000000...) и подает результирующую последовательность в РССК2. Поэтому, даже хотя увеличение веса Хэмминга останавливается в РССК1, вес Хэмминга постоянно увеличивается в РССК2 так, что общее свободное расстояние турбокодера увеличивается. Это происходит потому, что полином обратной связи, имеющий тип фильтра с бесконечной импульсной характеристикой (БИХ), постоянно вырабатывает бесконечный выходной символ "1", даже для одного информационного символа "1". Уравнение 1, приводимое ниже, показывает зависимость между РССК1 и РССК2 в терминах веса Хэмминга или свободного расстояния турбокодера.

Уравнение (1):
ВХ (выходная кодовая последовательность)=ВХ(кодовой последовательности РССК1) + ВХ(кодовой последовательности РССК2), где ВХ - вес Хэмминга.

Из Уравнения (1) следует, что баланс веса Хэмминга между РССК1 и РССК2 очень важен. В частности, минимальное свободное расстояние турбокода вырабатывается для минимального веса Хэмминга входного информационного слова, когда в расчет берется характеристика БИХ (бесконечной импульсной характеристики) РССК-кодера. В принципе, минимальное свободное расстояние обеспечивается, когда входное информационное слово имеет вес Хэмминга, равный 2, как упоминалось ранее.

Однако, как описано выше, минимальное свободное расстояние возникает, когда входное информационное слово имеет вес Хэмминга, равный 3, 4, 5,..., а также, когда входное информационное слово имеет вес Хэмминга, равный 2. Это происходит, когда входное информационное слово принимается на основе кадровых блоков, как в следующем примере.

Например, когда только информационный бит, расположенный в последней позиции входного информационного слова, т.е. последней позиции кадра, равен "1", а все остальные информационные биты равны 0, вес Хэмминга входного информационного слова становится равным 1. В этом случае, количество символов "1", выводимых из РССК1, становится очень малым, поскольку более нет входного информационного слова. Разумеется, когда используются нулевые концевые биты, существует два символа, но они используются независимо, а не подвергаются турбоперемежению. Поэтому здесь предполагается, что вес слегка увеличивается. Поскольку прибавляется постоянный вес, он исключается из анализа перемежителя. В этом случае отметим из Уравнения (1), что РССК2 должен вырабатывать большое количество выходных символов "1" для увеличения общего свободного расстояния.

Со ссылками на фиг.4-10 ниже приведено сравнительное описание с учетом проблем предшествующего уровня техники и решений этих проблем.

На фиг.4-10 заштрихованные участки показывают позиции, в которых входящие информационные биты имеют значение "1", a остальные участки обозначают позиции, в которых входящие информационные биты имеют значение "0".

Если, как показано на фиг.4, турбоперемежитель сдвигает (или переставляет) позицию входного информационного слова, когда исходным символом РССК1 является "1", в последнюю позицию кадра после перемежения, количество выходных символов "1", вырабатываемых РССК2, будет очень мало. В этом случае, поскольку РССК1 и РССК2 вырабатывают очень малое количество выходных символов "1" в соответствии с Уравнением (1), общее свободное расстояние серьезно уменьшается. Тем не менее, если, как показано на фиг.5, турбоперемежитель сдвигает позицию входного информационного слова, в котором исходным символом РССК1 является "1", в первую позицию или в позицию, расположенную рядом с ведущей позицией кадра после перемежения, количество выходных символов "1", вырабатываемых РССК2, будет увеличиваться. Это происходит потому, что множество символов "1" выводятся через (N(размер перемежителя) - h(количество "1")) переходов состояний кодера РССК2. В этом случае РССК2 вырабатывает большое количество выходных символов "1", тем самым увеличивая общее свободное расстояние.

Вдобавок к уменьшенному свободному расстоянию, возникающему, когда внутренний перемежитель сдвигает входной информационный бит "1", расположенный в последней позиции кадра, в последнюю позицию кадра, как показано на фиг.4, если один из двух информационных битов с "1", расположенных в конечной позиции кадра, все еще расположены в конечной позиции кадра или рядом с ней даже после перемежения, как показано на фиг.6, общее свободное расстояние будет уменьшаться.

Например, если внутренний перемежитель действует в кадровом режиме, показанном на фиг.6, где два символа, расположенные в конечной позиции кадра, являются единицами, а остальные символы являются нулями, то вес Хэмминга входного информационного слова равен 2. Даже в этом случае количество выходных символов, равных "1", вырабатываемых РССК1, становится очень мало, поскольку не имеется больше входного информационного бита. Поэтому по Уравнению (1) РССК2 должен вырабатывать большое количество выходных символов "1" для увеличения общего свободного расстояния. Однако если, как показано на фиг.6, турбоперемежитель сдвигает позицию двух вышеупомянутых символов в конечную позицию (или рядом с конечной позицией) кадра даже после перемежения, РССК2 также будет вырабатывать малое количество выходных символов "1". Однако если, как показано на фиг.7, турбоперемежитель сдвигает позицию двух вышеупомянутых символов в начальную позицию (или рядом с начальной позицией) кадра, РССК2 будет вырабатывать большое количество символов "1". То есть кодер РССК2 выдает множество символов "1" через (N-h) переходов состояний (N = размер перемежителя, h = количество символов "1"). В этом случае, следовательно, РССК2 вырабатывает большее количество выходных символов "1", тем самым увеличивая общее свободное расстояние.

Этот принцип может быть распространен на случай, в котором турбоперемежитель действует в кадровом режиме, показанном на фиг.8, в котором множество информационных битов со значением "1" присутствует в конечном периоде (или на конечном отрезке) кадра, а все другие информационные биты имеют значение "0". Даже в этом случае общее свободное расстояние увеличивается путем сдвига информационных битов, присутствующих в конечной позиции кадра, в начальную позицию кадра или в более близкие к начальной позиции, как показано на фиг.8. Разумеется, поскольку турбокод является линейным блоковым кодом, даже новое информационное слово, полученное путем добавления ненулевого информационного слова к такому информационному слову, имеет то же самое свойство. Поэтому нижеследующее описание основывается на информационном слове из всех нулей.

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

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

Условие 2: информационные биты, соответствующие последней позиции кадра, должны сдвигаться в позицию, предшествующую последней позиции (если возможно, в начальную позицию кадра), путем перемежения для увеличения свободного расстояния турбокода.

Эти условия применимы к двумерному турбоперемежителю, а также к вышеописанному одномерному перемежителю. Одномерный перемежитель выполняет перемежение, рассматривая входной информационный кадр в качестве группы, как показано на фиг.4-8. Двумерный перемежитель выполняет перемежение путем разделения входного информационного кадра на множество групп. Фиг.9 показывает двумерное перемежение, при котором входное информационное слово имеет вес Хэмминга, равный 1.

Как показано, входные информационные биты последовательно записываются в соответствующие группы (или строки). То есть входные информационные биты последовательно записываются в группы (или строки) r0, r1,...,r(R-1). В каждой группе входные информационные биты последовательно записываются слева направо. После этого турбоперемежающий алгоритм случайным образом меняет позиции R•C элементов (т. е. входных информационных битов), где R - количество строк, а С - количество столбцов или, что то же самое, количество информационных битов в группе. В этом случае предпочтительно разрабатывать турбоперемежающий алгоритм так, чтобы информационный бит, расположенный в последней позиции (или самой правой позиции) последней группы, передвигался во время вывода в самую первую позицию, если это возможно. Разумеется, в зависимости от порядка выбора групп входной информационный бит, расположенный в последней позиции, может сдвигаться в самую первую позицию соответствующей группы (или близко к ней). Условие (1) и Условие (2) могут быть нормированы в k-мерном турбоперемежителе (k>2) так же, как и в двумерном перемежителе.

Фиг. 10 показывает случай, в котором входное информационное слово имеет вес Хэмминга более 2. Как показано, информационные биты, расположенные в последней позиции последней группы, сдвигаются к начальным позициям последней группы путем перемежения. Разумеется, подробное правило сдвига (или перемежения) определяется в соответствии с алгоритмом для конкретного перемежителя. Изобретение представляет Условие (1) и Условие (2), которые обязательно должны быть соблюдены при определении правила перемежения.

Ниже описан ПП-перемежитель, имеющий проблемы, присущие известному перемежителю, а затем приведено описание решения проблем, которые имеет этот ПП-перемежитель.

На первой стадии (1) определяется число строк как R=10 в случае, когда число К входных информационных битов находится в пределах от 481 до 530, и R= 20 в случае, когда число К входных информационных битов является блоком любой другой длины, за исключением от 481 до 530, (2) определяется число столбцов С так, что в случае (1) С=р=53, где р=минимальное простое число, а в случае (2)
(i) находится минимальное простое число р такое, что 0≤(p+1)-K/R;
(ii) если (0≤p-K/R), то перейти к (iii), иначе С=р+1;
(iii) если (0≤p-1-K/R), то С=р-1, иначе С=р.

На второй стадии сначала будет описан Случай-Б, если С=р+1 по алгоритму перемежения для ПП-перемежителя, который был условно определен как турбоперемежитель UMTS. В приведенном ниже Уравнении (2) R обозначает число групп (или строк) и имеет значение R=10 или R=20. С обозначает размер каждой группы и определяется простым числом р, ближайшим к отношению R/K, определенному на Стадии (1) в соответствии с величиной K/R, где К является размером входных информационных битов в кадре. В Случае-Б С всегда равно р+1. Поэтому размер ПП-перемежителя принимает значение, определяемое R•C, которое больше, чем С. C_j(i) обозначает позицию информационных битов, полученную путем случайной перестановки позиции входных информационных битов в группе для i-й группы, где i= 0, 1, 2, 3,...,р. В дополнение, P_j обозначает начальную величину рандомизации, заданную для вектора j-й строки, и изначально задается алгоритмом.

Уравнение (2)
Б-1) Первообразный корень g0 выбирается из заданной таблицы констант инициализации рандомизации (3GPP TS 25.212 Табл. 2; таблица простых р и связанных простых корней) так, что д0 является простым корнем поля, основанного на простом p.

Б-2) Формируется базовая последовательность C(i) для использования для рандомизации вектора строки с использованием следующей формулы:
C(i)=[g0•C(i-1)]mod р, i=1, 2, 3,...р-2, С(0)=1
Б-3) Выбирается множество минимальных простых целых чисел {q_j, j=0, 1, 2, ...R-1} такое, что HOД{q_j, р-1}=1, q_j>6 и q_j>q_(j-1), где НОД - наибольший общий делитель, a q₀=1.

Б-4) { p_j, j=0, 1, 2,..., R-1}, являющееся новым множеством простых чисел, вычисляется из {q_j, j=0, 1, 2,...,R-1} так, что p_p(j)=q_j, где j=0,1,... , R-1, и p(j) является схемой межстроковой перестановки, определяемой на третьей стадии.

Б-5) Определяются элементы j-й межстроковой перестановки по следующему способу:
C_j(i)=C([i•p_j]mod(p-1)), i=0, 1, 2, 3,...,р-2;
C_j(p-1)=0 и
C_j(р)=р.

На третьей стадии выполняется строковая перестановка на основании следующих структур: p(j) (j=0, 1, 2,...,R-1), где p(j) является начальной позицией строки, ставшей после перестановки j-й. Эти структуры используются следующим образом: если количество К входных информационных битов находится в пределах от 320 до 480, выполняется структура р_A выбора группы, если количество К входных информационных битов находится в пределах от 481 до 530, выполняется структура р_B выбора группы, если количество К входных информационных битов находится в пределах от 531 до 2280, выполняется структура р_A выбора группы, если количество К входных информационных битов находится в пределах от 2281 до 2480, выполняется структура р_Б выбора группы, если количество К входных информационных битов находится в пределах от 2481 до 3160, выполняется структура р_A выбора группы, если количество К входных информационных битов находится в пределах от 3161 до 3210, выполняется структура р_Б выбора группы, а если количество К входных информационных битов находится в пределах от 3211 до 5114, выполняется структура р_А выбора группы. Структура выбора группы такова:
р_А: { 19, 9, 14, 4, 0, 2, 5, 7, 12, 18, 10, 8, 13, 17, 3, 1, 16, 6, 15, 11} для R=20;
р_Б: { 19, 9, 14, 4, 0, 2, 5, 7, 12, 18, 16, 13, 17, 15, 3, 1, 6, 11, 8, 10} для R=20;
р_В: {9, 8, 7, 6, 5, 4, 3, 2, 1, 0} для R=10.

Здесь следует отметить, что последняя операция Б-5) определяется как C_j(p)= p. To есть это означает, что если позицией входного информационного бита до перемежения была р, то входной информационный бит остается в позиции р после ПП-перемежения. Следовательно, для последней группы (j=19) информационные биты C_R-1(Р)=C₁₉(р), находящиеся в последней позиции, сохраняют ту же позицию i=P, являющуюся последней позицией 19-й группы. Поэтому Условие (2) построения турбоперемежителя не удовлетворяется.

То есть для решения имеющейся у ПП-перемежителя проблемы, шаг Б-5) алгоритма должен быть модифицирован следующим образом. Изобретение предлагает шесть способов, от Б-5-1) до Б-5-6), в качестве примера. Оптимальное решение может быть выбрано путем моделирования в свете свойств турбоперемежителя.

Выбирается один из 6 следующих способов.

Б-5-1) Меняются позиции C_R-1(0) и C_R-1(p). R=10 или 20.

Б-5-2) Меняются позиции C_R-1(p-1) и C_R-1(p). R=10 или 20.

Б-5-3) Для каждого j меняются позиции C_j(0) и C_j (р). j=0, 1, 2...,R-1.

Б-5-4) Для каждого j меняются позиции C_j(p-1) и C_j(р). j=0, 1, 2,..., R-1.

Б-5-5) Для каждого j определяется оптимальная позиция k для перемежения позиций C_j(k) и C_j(p) в используемом алгоритме перемежения.

Б-5-6) Для (R-1)-й строки определяется оптимальная позиция k для перемежения позиций C_R-1(k) и C_R-1(p) в используемом алгоритме перемежения.

Фиг. 11 и 12 показывают функциональную схему и блок-схему алгоритма, соответственно, согласно выполнению настоящего изобретения.

По фиг. 11 блок 912 перестановки вектора-строки (или генератор индекса перестановки вектора-строки) вырабатывает индекс для выбора вектора-строки в соответствии с отсчетом счетчика 911 строки и подает выработанный индекс в верхний адресный буфер адресного буфера 918. Блок 912 перестановки вектора-строки является групповым селектором для последовательного или случайного выбора разделенных групп, если входное информационное слово делится на множество групп. Блок 914 перестановки вектора-столбца (или генератор индекса перестановки вектора-столбца) вырабатывает, в зависимости от модифицированного алгоритма 915 ПП, индекс для перестановки позиций элементов соответствующего вектора-строки (или группы) в соответствии с отсчетом счетчика 913 столбца и подает выработанный индекс в нижний адресный буфер адресного буфера 918. Блок 914 перестановки вектора-столбца является рандомизатором для перестановки в группе позиций информационных битов, которые были последовательно сохранены в порядке ввода, в соответствии с заданным правилом. ОЗУ (Оперативное Запоминающее Устройство) 917 сохраняет временные данные, выработанные в ходе действия программы. Таблица 916 преобразований хранит параметры для перемежения и первообразный корень. Адреса, полученные путем перестановки строк и перестановки столбцов (т.е. адреса, сохраненные в адресном буфере 918), используются в качестве адресов для перемежения.

Фиг. 12 показывает пошаговую схему модифицированного алгоритма ПП. Приводимое ниже описание относится ко второй стадии, Случаю-Б, алгоритма ПП. По фиг. 12 первообразный корень g0 выбирается из заданной таблицы констант инициализации на шаге 1011. После этого на шаге 1013 вырабатывается базовая последовательность C(i) для рандомизации элементов (или информационных битов) группы с помощью следующей формулы:
C(i)=[g0•C(i-1)]mod р, i=0, 1, 2, 3,...,р-2, С(0)=1
После этого на шаге 1015 рассчитывается множество минимальных простых чисел { q_j, j=0, 1, 2,...,R-1}, заданное для алгоритма. Затем на шаге 1017 рассчитывается множество простых чисел {p_j, j=0, 1, 2,...,R-1} исходя из рассчитанного множества минимальных простых чисел. Затем на шаге 1019 элементы j-й группы рандомизируются по следующему способу:
C_j(i)=c([i•p_j]mod(p-1), i=0, 1, 2, 3,...,(р-2);
C_j(p-1)=0.

Здесь, для увеличения минимального свободного расстояния турбокодера при рандомизации элементов группы, выбирается один из Б-5-1) - Б-5-6) для перестановки (или сдвига) информационных битов, присутствующих в последней позиции кадра, в другие позиции после перемежения.

Б-5-1) означает, что позиции первого информационного бита и последнего информационного бита в последней группе меняются местами друг с другом. Б-5-2) означает, что последние два информационных бита последней группы меняются друг с другом. Б-5-3) означает, что для каждой группы информационный бит, находящийся в последней позиции, и информационный бит, находящийся в начальной позиции, меняются местами друг с другом. Б-5-4) означает, что для каждой группы меняются позиции последних двух информационных битов. Б-5-5) означает, что для каждой группы определяется оптимальная позиция k для заданного правила перемежения для замены позиции информационного бита, находящегося в последней позиции каждой строки, позицией информационного бита, находящегося в позиции k. Наконец, Б-5-6) означает, что для последней группы определяется оптимальная позиция k для заданного правила перемежения для замены позиции информационного бита, находящегося в последней позиции, позицией информационного бита, находящегося в позиции k.

Путем применения модифицированного алгоритма к ПП-перемежителю можно предотвратить уменьшение свободного расстояния турбокодера. Приводимая в конце описания Таблица 2 показывает спектр веса ПП-перемежителя до модификации, а приводимая в конце описания Таблица 3 показывает спектр веса ПП-перемежителя после модификации.

В Таблицах 2 и 3 К обозначает размер входного информационного кадра, Рсвоб(1) обозначает свободное расстояние, рассчитанное с помощью ККИП, для которого входное информационное слово имеет вес Хэмминга, равный 1, а Рсвоб(2) обозначает свободное расстояние, рассчитанное с помощью ККИП, для которого входное информационное слово имеет вес Хэмминга, равный 2. Например, для К= 600Б Рсвоб(1) исходного ПП-перемежителя в Таблице 2 обозначено как 25/39/49/53/57/. . . , и это означает, что минимальное свободное расстояние равно 25, а следующее минимальное свободное расстояние равно 39. Подобным же образом, Рсвоб(2)==38/38/42... означает, что минимальное свободное расстояние равно 38. Поэтому отметим, что минимальное свободное расстояние определяется в соответствии со свободным расстоянием по ККИП с весом Хэмминга, равным 1. Для предотвращения уменьшения свободного расстояния ККИП с весом Хэмминга, равным 1, изобретение использует в данном примере способ Б-5-1). То есть Рсвоб(1) улучшается посредством удаления ККИП с весом Хэмминга, равным 1.

Приводимая в конце описания Таблица 2 показывает весовой спектр ПП-перемежителя до модификации.

Приводимая в конце описания Таблица 3 показывает весовой спектр ПП-перемножителя после модификации.

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

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

Формула изобретения

1. Турбокодер, содержащий первый кодер для кодирования кадра входных информационных битов для генерирования первых кодированных символов, перемежитель для приема информационных битов и такого перемежения позиций информационных битов, чтобы информационный бит, находящийся в последней позиции кадра, сдвигался в позицию, предшествующую последней позиции, для исключения выработки критической комбинации информационной последовательности (ККИП), и второй кодер для кодирования перемеженных информационных битов для выработки вторых кодированных символов.

2. Турбокодер по п. 1, отличающийся тем, что перемежитель содержит контроллер для последовательной записи К информационных битов в памяти перемежителя и разделения информационных битов на R групп по С информационных битов в каждой, для перестановки адреса информационного бита, записанного в j-й строке (где j= 0, 1, 2, . . . , R-1), в позицию C_j(i) в этой строке в соответствии со следующим заданным алгоритмом:
i) C(i)= [g0•C(i-1)] mod р, i= 1, 2, . . . , p-2 и С(0)= 1;
ii) C_j(i)= C([i•p_j] mod(p-1));
j= 0, 1, 2, . . . , (R-1), i= 0, 1, 2, . . . , (p-1), C_j(p-1)= 0, и C_j(p)= p;
iii) поменять местами C_R-1(p) и C_r-1(0),
где р - простое число, ближайшее к K/R;
g0 - первообразный корень, указывающий заранее заданное число, соответствующее р;
p_j - множество простых чисел.

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

4. Турбокодер по п. 3, отличающийся тем, что рандомизатор меняет местами адрес информационного бита, находящегося в последней позиции последней группы, с адресом информационного бита, находящегося в первой позиции последней группы.

5. Устройство для перестановки адресов входного кадра информационных битов, имеющего R групп по С информационных битов в каждой, в первичном перемежителе (ПП), используемом в качестве внутреннего перемежителя для турбокодера, содержащее память перемежителя для последовательного сохранения кадра информационных битов, рандомизатор для перестановки адресов информационных битов и для изменения адреса последнего информационного бита в позицию, предшествующую этой позиции в последней группе.

6. Устройство по п. 5, отличающееся тем, что рандомизатор меняет местами позицию информационного бита, находящегося в последней позиции последней группы, с позицией информационного бита, находящегося в первой позиции последней группы.

7. Устройство для перемежения кадра из К информационных битов, имеющего R групп по С информационных битов в каждой, в первичном перемежителе, используемом в качестве внутреннего перемежителя для турбо кодера, содержащее контроллер для последовательной записи входных информационных битов в памяти перемежителя и перестановки позиции информационного бита, записанного в j-й строке (где j= 0, 1, 2, . . . , R-1), в позицию C_j(i) в этой строке в соответствии со следующим заданным алгоритмом:
i) выполнить перестановку базовой последовательности
C(i)= [g0•C(i-1)] mod p, i= 1, 2, . . . . (p-2) и С(0)= 1;
ii) выполнить перестановку строк
C_j(i)= C([i•p_j] mod(p-1)),
j= 0, 1, 2, . . . , (R-1), i= 0, 1, 2, . . . (p-1), C_j(p-1)= 0 и C_j(p)= p,
iii) поменять местами C_r-1(p) и C_r-1(0),
где р - простое число, ближайшее к K/R;
g0 - первообразный корень, указывающий заранее заданное число, соответствующее р;
p_j - множество простых чисел.

8. Способ двумерного перемежения, содержащий следующие шаги: последовательное сохранение кадра из К входных информационных битов в памяти перемежителя и разделение информационных битов на R групп по С информационных битов в каждой, перестановка адресов информационных битов каждой группы и изменение адреса информационного бита, находящегося в последней позиции оследней группы, на адрес, предшествующий последней позиции.

9. Способ двумерного перемежения по п. 8, отличающийся тем, что перестановка содержит следующие шаги: определение минимального простого числа р, наиболее близкого к K/R, последовательная запись входных последовательностей информационных битов кадра в памяти перемежителя, выбор первообразного корня g0, соответствующего минимальному простому числу р, и генерирование базовой последовательности c(i) для внутристроковой перестановки входных последовательностей, записанных в строки, в соответствии с
C(i)= [g0•C(i-1)] mod p, i= 1, 2, . . . , (p-2) и С(0)= 1;
вычисление множества минимальных простых чисел { q_j} (j= 0, I, 2, . . . , R-1) путем определения
НОД{ q_j, р-1} = 1;
q_j>6, q_j>q_(j-i),
где НОД - наибольший общий делитель;
q₀= 1,
внутристроковая перестановка { qj} с помощью
p_p(j)= q_j, j= 0, 1, . . . , R-1,
где P(j) обозначает заранее заданный порядок выбора для выбора R рядов,
при С= р+1, перестановка последовательностей в j-й строке в соответствии с
C_j(i)= C([i•p_j] mod(p-1)),
где j= 0, 1, 2, . . . , (R-1), i= 0, 1, 2, . . . , (p-1), q(p-1)= 0 и G_j(p)= p,
и если (К= С•R), то C_R-1(p) меняется местами с C_R-1(0).

10. Способ двумерного перемежения по п. 8, отличающийся тем, что адрес информационного бита, находящегося в последней позиции последней группы, меняется с адресом информационного бита, находящегося в первой позиции последней группы.

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

12. Способ двумерного перемежения по п. 11, отличающийся тем, что входная последовательность, записанная в последней позиции последней группы, заменяется входной последовательностью, записанной в первой позиции последней группы.

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

14. Способ по п. 13, отличающийся тем, что позиция информационного бита, находящегося в последней позиции последней группы, меняется местами с информационным битом, находящимся в первой позиции последней группы.

15. Способ по п. 13, отличающийся тем, что на шаге а) и б) позиции информационных битов в кадре, записанных в j-й строке (где= 0, 1, 2, . . . R-1), переставляются с позициями C_j(i) в этой строке в соответствии с заданным следующими шагами алгоритмом:
i) вычислить C(i)= [g0•C(i-1)] mod p, i= 1, 2, . . . , (p-2) и С(0)= 1;
ii) вычислить C_j(i)= C([i•p_j] mod (р-1)), где
j= 0, 1, 2, . . . , (R-1), i= 0, 1, 2, . . . , (p-1), C_j(p-1)= 0 и C_j(p)= p;
iii) поменять местами C_R-1(p) и С_r-1(0),
где p - простое число, ближайшее к K/R;
g0 - первообразный корень, указывающий заранее заданное число, соответствующее p;
p_j - множество простых чисел;
C_j(i) - входная битовая позиция i-го вывода после перестановки j-й строки.

16. Способ двумерного перемежения, содержащий следующие шаги: последовательная запись входных последовательностей К информационных битов кадра в прямоугольную матрицу R•С; выбор первообразного корня g0, соответствующего минимальному простому числу р, и генерирование базовой последовательности c(i) для внутристроковой перестановки входных последовательностей, записанных в строки, в соответствии с
C(i)= [g0•C(i-1)] mod р, i= 1, 2, . . . , (р-2) и С(0)= 1,
вычисление множества минимальных простых чисел { q_j} (j= 0, 1, 2, . . . , R-1) путем определения
НОД{ q_j, р-1} = 1;
q_j>6, q_j>q_(j-1),
где НОД - наибольший общий делитель;
q₀= 1;
внутристроковая перестановка { q_j} с помощью
p_p(j)= q_j, j= 0, 1, . . . , R-1
где P(j) указывает заранее заданный порядок выбора для выбора R рядов,
при С= р+1, перестановка последовательностей в j-й строке в соответствии с
C_j(i)= C([i•p_j] mod(p-1)),
где j= 0, 1, 2, . . . , (R-1), i= 0, 1, 2, . . . , (p-1), C_j(p-1)= 0 и C_j(p)= p,
и если (K= C•R), то С_R-1 (Р) меняется местами с С_r-1(0), выбор R строк в соответствии с заранее заданным порядком P(j), и выбор одной входной последовательности из выбранной строки и предоставление выбранной входной последовательности в качестве адреса считывания для перемежения информационных битов входного кадра.

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7, Рисунок 8, Рисунок 9, Рисунок 10, Рисунок 11, Рисунок 12, Рисунок 13, Рисунок 14, Рисунок 15, Рисунок 16, Рисунок 17, Рисунок 18, Рисунок 19