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

 

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

Область техники, к которой относится изобретение

Настоящее изобретение имеет отношение вообще к области кодирования для коммуникационных систем и более конкретно - к перемежителям для турбокодеров.

Уровень техники

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

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

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

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

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

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

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

Данные, представленные в многоуровневой шкале, называются "гибкими данными", и итеративное декодирование является обычно гибким входом/гибким выходом, т.е. процесс декодирования принимает последовательность входных сигналов, соответствующих вероятностям для значений бит, и предоставляет в качестве выходного сигнала скорректированные вероятности, принимая во внимание ограничения кода. Обычно декодер, который выполняет итеративное декодирование, использует гибкие данные из предыдущих итераций для декодирования гибких данных, считанных приемником. Во время итеративного декодирования многокомпонентных кодов декодер использует результаты декодирования одного кода для улучшения декодирования второго кода. Когда используются параллельные кодеры, как в турбокодировании, два соответствующих декодера могут удобно использоваться параллельно для этой цели. Такое итеративное декодирование выполняется в течение множества итераций до тех пор, пока полагают, что гибкие данные близко представляют передаваемые данные. Тем битам, которые имеют вероятность, указывающую, что они находятся ближе к единице (например, между 0 и 31 на шкале, описанной выше), присваивается двоичный ноль, а остальным битам присваивается двоичная единица.

"Турбокодирование" представляет важное усовершенствование в области кодирования с упреждающим исправлением ошибок (УИО). Имеется много вариантов турбокодирования, но большинство типов турбокодирования использует многочисленные операции кодирования, разделенные операциями перемежения, объединенные использованием итеративного декодирования. Это объединение обеспечивает ранее недоступную эффективность относительно допуска шума в коммуникационных системах. А именно, турбокодирование дает возможность коммуникаций на уровнях спектральной плотности, отношения энергии на бит к мощности шума (Е_b/No), которые были неприемлемы при использовании существующих способов упреждающего исправления ошибок.

Многие коммуникационные системы используют способы упреждающего исправления ошибок и, следовательно, извлекли бы выгоду из использования турбокодирования. Например, турбокоды могли бы улучшить производительность беспроводных спутниковых линий связи, в которых ограниченная передаваемая мощность по исходящей линии связи (линии связи спутник-наземная станция) спутника неизбежно влечет за собой системы приемника, которые могут работать на низких уровнях Eb/No.

Цифровые беспроводные телекоммуникационные системы, например, такие как, цифровые сотовые и телефонные системы ПСС (персональные системы связи), также используют упреждающее исправление ошибок. Например, Ассоциация Промышленности средств связи опубликовала стандарт воздушного интерфейса, временный стандарт TIA/EIA 95 и его производные, такие как, например, IS-95B (далее совместно называемые IS-95), которые определяют цифровую беспроводную коммуникационную систему, которая использует сверточное кодирование для обеспечения выигрыша при кодировании для увеличения пропускной способности системы. Система и способ для обработки радиочастотных (РЧ) сигналов, по существу, в соответствии с использованием стандарта IS-95,\ описаны в патенте США №5103459.

Имеется непрерывная тенденция в промышленности средств связи постоянного улучшения выигрышей при кодировании. В традиционных цифровых беспроводных коммуникационных системах было обнаружено, что последовательный перемежитель для турбокодирования может быть выгодно реализован с помощью конгруентной случайной последовательности. В данной области техники известно, что однородная случайная последовательность может быть сгенерирована при использовании алгоритма линейной конгруентной рекурсии. Смотри, например, 2 D/ Knuth, The Art of Computer Programming (1969) (описывающую генерирование псевдослучайных чисел с помощью линейной конгруэнтной рекурсии). Также было обнаружено, что параллельный турбокодер, использующий двумерный перемежитель (т.е. перемежитель, организованный как прямоугольный массив данных, содержащий строки и столбцы), обычно превосходит параллельный турбокодер, имеющий одномерный перемежитель (т.е. перемежитель, в котором данные организованы как один линейный массив), с точки зрения выигрыша при кодировании.

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

Сущность изобретения

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

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

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

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

Краткое описание чертежей

Фиг.1 - блок-схема параллельного составного турбокодера.

Фиг.2 - блок-схема перемежителя, который может быть использован в параллельном составном турбокодере фиг.1.

Фиг.3 - блок-схема составного кодера, который может быть использован вместе с перемежителем фиг.2.

Подробное описание предпочтительных вариантов осуществления изобретения

В соответствии с одним вариантом осуществления изобретения, как проиллюстрировано на фиг.1, параллельный составной турбокодер 10, или турбокодер 10, содержит первый и второй кодеры 12, 14, перемежитель 16 и мультиплексор 18. Первый кодер 12 и перемежитель 16 выполнены с возможностью приема входных данных 20 кодера, которые обычно являются пользовательской информацией или данными управления. Первый кодер 12 выводит систематические символы 22, которые являются обычно копией исходных входных битов 20, и символы 24 контроля по четности. Второй кодер 14 выполнен с возможностью приема перемежающегося выходного сигнала 26 перемежителя 16 и для вывода второго множества символов 28 контроля по четности. Систематические символы (не изображены), генерируемые вторым кодером 14, сжимаются, а остальные соответствующие выходные сигналы 22, 24, 28 первого и второго кодеров 12, 14 мультиплексируются мультиплексором 18 в поток 30 выходных данных.

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

Первый и второй кодеры 12, 14 могут быть кодерами различных типов, известными в данной области техники, включая блочные кодеры и сверточные кодеры. Примерные блочные кодеры и сверточные кодеры описаны в статье Бернарда Склара в журнале Digital Communication, 245-380 (1988). Первый и второй кодеры 12, 14 являются преимущественно сверточными кодерами с относительно малыми ограниченными длинами К, такими как, например, К=4, таким образом, обеспечивая уменьшенную сложность, поскольку малые ограниченные длины уменьшают сложность соответствующих декодеров (не изображены). Первый и второй кодеры 12, 14 также преимущественно являются рекурсивными систематическими сверточными (РСС) кодерами, которые известны в данной области техники. Перемежитель 16 преимущественно является двумерным перемежителем, как описано ниже.

Обычно первый и второй кодеры 12, 14 выводят два символа 24, 28 контроля по четности для каждого принимаемого бита 20, давая скорость кодирования R=1/2 для каждого кодера 12, 14. Тем не менее, общая скорость кодирования для турбокодера 10 равна 1/3, поскольку систематический бит из второго кодера прокалывается.

Как изображено на фиг.2, двумерный (2-D) перемежитель 100 линейной конгруэнтной последовательности (ЛКП) в соответствии с одним вариантом осуществления изобретения содержит четыре справочных таблицы (СТ) 102, 104, 106, 108, семь двухвходовых мультиплексоров (МП) 110, 112, 114, 116, 118, 120, 122 и R-входовый мультиплексор 124, счетчик 126 строки, первый и второй логические блоки 128, 130 инвертирования бит, модуль 132 проверки правильности адреса, множество R регистров 134, 136, 138, 140 индекса столбца или строки (изображенных для простоты как четыре регистра), регистр 142 для маркировки сброса индекса столбца, первый и второй k-битовые мультиплексоры 144, 146 и четыре k-битовых сумматора 148, 150, 152, 154. Генератор 156 рекурсии ЛКП изображен пунктирной линией. Перемежитель 100 может использоваться параллельно составному турбокодеру фиг.1 или альтернативно перемежитель 100 может использоваться последовательно составному турбокодеру, в котором перемежитель 100 расположен снаружи или внутри составных кодеров, что очевидно специалистам в данной области техники.

Размер перемежителя 100 равен N, которое меньше или равно 2^m и больше, чем 2^m-l. Число строк R, умноженное на число столбцов С, равно 2^m. Число столбцов С равно 2^k, т.e. k=log₂ С. Число строк R равно 2^r, т.е. r=log₂ R.

Модуль 132 проверки правильности адреса может быть преимущественно реализован в виде логической схемы на дискретных вентильных элементах, сконфигурированной как сдвиговый регистр и сумматор. Модуль 132 проверки правильности адреса служит для проверки, меньше ли вход X, чем произведение номера С столбца и входа Y (индекса строки), сложенных с входом Z (индексом столбца), выполняя, например, функцию сдвига и суммирования. Модуль 132 проверки правильности адреса служит для генерирования маркера, который указывает, является ли адрес неправильным, т.е. содержит ли адрес избыточные биты степени 2 (т.е. находится ли размер перемежителя между последовательными степенями 2), которые должны быть отброшены.

Генератор 156 рекурсии ЛКП служит для псевдослучайного переупорядочения, или тасования, значений бит, содержащихся в каждой строке перемежителя 100, как описано ниже, с помощью приема значения номера строки на входах в четыре СТ 102, 104, 106, 108 и генерирования индекса столбца (входа Z в модуль 132 проверки правильности адреса). Специалистам в данной области техники будет понятно, что в параллельном составном турбокодере, таком как проиллюстрирован на фиг.1, физическое переупорядочение элементов данных можно преимущественно обойти в пользу использования псевдослучайно генерируемой ЛКП на считывании, адресуемом вторым кодером. Первый и второй логические блоки 128, 130 инвертирования бит служат для переупорядочения, или тасования, строк в перемежителе 100 в соответствии с заданным правилом инвертирования бит, как описано ниже и известно в данной области техники.

СТ 102, 104, 106, 108 могут быть реализованы в виде некоторого запоминающего средства, известного в данной области техники. Первая СТ 102 используется для хранения значений коэффициента "с". Вторая СТ 104 используется для хранения значений коэффициента "а". Третья СТ 106 используется для хранения значений коэффициента "а", взятого в степени коэффициента "b". Четвертая СТ 108 используется для хранения значений x(-1). Размер каждой СТ 102, 104, 106, 108 равен r x k битов. Общими требованиями к памяти для перемежителя 100 являются 4r x k битов плюс r x k битов регистров для регистров 134, 136, 138, 140.

Регистр 142 принимает значение бит, определяющее номер строки, который первоначально устанавливается равным R-1. С каждым циклом обработки регистр 142 выводит значение бит, означающее номер столбца, который первоначально устанавливается не равным нулю. Регистр 142, таким образом, служит для сброса индекса столбца каждый раз, когда номер строки циклически проходит через все строки.

С каждым циклом обработки входной МП 110 генерирует значение либо 1, либо -1, в зависимости от того, установлен ли маркер выполнения в обратном направлении. Это значение подается в сумматор 148, который суммирует это значение со значением бита, обозначенного NextRow (следующая строка).

Результирующая сумма подается на вход данных счетчика 126 строки. Значение 1 подается на второй вход счетчика 126 строки. Счетчик 126 строки создает значение строки (хранимое первоначально как R-1 в регистре 142), которое подается во второй логический блок 130 инвертирования бит. Значение строки также подается в каждую из СТ 102, 104, 106, 108. Значение строки также подается в сумматор 150, который суммирует значение строки со значением 1 и подает результирующую сумму в первый логический блок 128 инвертирования бит. Эта результирующая сумма также подается на первый вход МП 112.

С каждым циклом обработки первый логический блок 128 инвертирования бит подает некоторое значение на первый вход МП 114. Второй логический блок 130 инвертирования бит подает значение индекса строки на второй вход МП 114, а также на вход Y модуля 132 проверки правильности адреса. Модуль 132 проверки правильности адреса принимает значение N на входе X. Модуль 132 проверки правильности адреса принимает значение "а", основанное на хранимых коэффициентах, на входе Z. Модуль 132 проверки правильности адреса ЛКП вычисляет произведение С и значения входа Y, суммирует произведение со значением входа 2 и проверяет, является ли результат больше или равным значению N на входе X. Если вычисленное значение больше или равно N, модуль 132 проверки правильности адреса выводит значение 1. Иначе значение выхода равно 0. Выходное значение является маркером, обозначенным Addr_GT_N, который, когда установлен в 1, означает, что размер перемежителя находится между последовательными степенями 2 так, что избыточные биты после более низкой степени 2 должны быть отброшены.

Значение Addr_GT_N подается в виде селекторного входного сигнала в МП 112, 114, 120 и 122. МП 112 выбирает свой первый вход, если значение Addr_GT_N установлено в 1. Выбранный входной сигнал, который выводится из МП 112, является перемежающимся значением NextRow. МП 114 выбирает свой первый вход, если значенеие Addr_GT_N установлено в 1. Выбранный входной сигнал, который выводится из МП 114, представляет значение индекса конечной строки.

Генерация рекурсии ЛКП выполняется следующим образом. С каждым циклом обработки k-битовое значение, представляющее коэффициент "с", посылается из первой СТ 102 в k-битовый сумматор пути данных. Значение "а" посылается из второй СТ 104 на первый вход МП 116. Значение, представляющее "а", взятое в степени "b", посылается из третьей СТ 106 на второй вход МП 116. МП 116 принимает маркер RunBackwards (выполнения в обратном порядке) на селекторном входе. Если значение RunBackwards равно 1, МП 116 выбирает свой второй вход и подает выбранное значение, k-битовое значение, в умножитель 144. Иначе МП 116 подает свой первый входной сигнал, k-битовое значение, в умножитель 144. Значение x(-1) посылается из четвертой СТ 108 на первый вход МП 118. МП 118 принимает на втором входе k-битовое значение, выведенное из МП 124. МП 118 принимает значение индекса столбца в качестве селекторного индекса. Значение индекса столбца первоначально устанавливается не равным нулю. Если значение индекса столбца равно 1, МП 118 выбирает свой второй вход. Иначе МП 118 выбирает свой первый вход. Выбранное входное значение, k-битовое значение, подается в умножитель 144. Результирующее произведение из умножителя 144 подается в k-битовый сумматор 152. Преимущественно k-битовый сумматор 152 пути данных является программируемым сумматором/вычитающим устройством, который известен в данной области техники. Когда перемежитель 100 производит выполнение в обратном направлении, сумматор 152 вычитает значение "с".

k-Битовый сумматор 152 подает выходное значение с каждым циклом обработки на вход Z модуля 132 проверки правильности адреса. Выходной сигнал сумматора 152 также подается на первый вход МП 120 и в каждый из регистров 136, 138, 140 первой по (R-1)-ой строки. Выходной сигнал сумматора 152 также подается как k-битовое выходное значение на первый вход МП 122.

МП 120 принимает второе входное значение из k-битового сумматора 154. Если селекторный вход МП 120 установлен в 1, МП 120 выбирает свой первый вход. Иначе МП 120 выбирает свой второй вход. Выбранный входной сигнал подается в регистр 134 нулевой строки. Каждый регистр 134, 136, 138, 140 строки подает выходное значение на соответствующие входы МП 124. Дополнительно выходное значение из регистра 134 нулевой строки подается в умножитель 146. МП 124 принимает значение строки (выходной сигнал счетчика 126 строки) на селекторном входе. Входной сигнал регистра строки, выбранный МП 124, зависит от значения строки на селекторном входе. Таким образом, каждый регистр 134, 136, 138, 140 строки обновляется, когда значение строки равно соответствующему номеру регистра строки, а регистр 134 нулевой строки также включается, когда маркер Addr_GT_N равен нулю.

k-Битовое начальное входное значение b для R=0 подается в умножитель 146. Умножитель 146 также принимает значение, выведенное из регистра 134 нулевой строки. Умножитель 146 умножает два принимаемых значения вместе и подает результирующее произведение в k-битовый сумматор 154. k-Битовый сумматор 154 пути данных также принимает начальное входное значение "с" для R=0. Преимущественно k-битовый сумматор 154 пути данных является программируемым сумматором/устройством вычитания, который известен в данной области техники. Когда перемежитель 100 работает в обратном направлении, сумматор 154 вычитает начальное значение "с". Сумматор 154 суммирует (или, как запрограммирован, вычитает) два принятых значения. Результирующая сумма, k-битовое значение, подается на второй вход МП 122.

МП 122 выбирает свой первый вход, если его селекторный вход установлен в 1. Иначе МП 122 выбирает свой второй вход. МП 122 выводит выбранный входной сигнал как значение индекса конечного столбца. Адрес для следующего значения бита является произведением R и значения индекса конечного столбца, выведенного из МП 122, просуммированного со значением индекса конечного столбца, выведенным из МП 114.

В одном варианте осуществления ЛКП с периодом М рекурсивно генерируется в соответствии со следующим тождеством:

Х(n+1)=(ах(n)+с)_modМ

с целыми "а", "с" и М, удовлетворяющими следующим трем условиям:

(1) "с" должно быть взаимно простым для М. (2) а-1 должно быть кратным р, где р - любое простое число, которое делит М. Когда М является кратным 4, а-1 должно быть кратно 4. (3) х(0) является значением начального числа, которое может быть любым целым. Для упрощения реализации М может быть преимущественно выбрано равным степени 2. Таким образом, "а" должно быть в виде 4р+1, в то время как "с" может быть взято как любое нечетное число. Следует заметить, что в то время как x(0) используется выше для обозначения начального условия, x(-1) используется для обозначения начального условия в варианте осуществления изобретения, описанном в связи с фиг.2. Никакое значение не должно придаваться различным используемым числам.

2-D перемежитель ЛКП в соответствии с одним вариантом осуществления изобретения определяется следующим образом: допуская размер перемежения равным К=2, перемежитель определяется как прямоугольная матрица с R строками и С столбцами, где R и С даются степенями 2. Перемежаемые данные записываются в матрицу по строкам. Строки данных сначала перестанавливаются (т.е. перемежаются) в соответствии с любым традиционным правилом перемежения. Преимущественно строки данных перестанавливаются в соответствии с правилом инвертирования бит, применяемым к индексу строки. Внутри каждой строки столбцы (т.е. элементы данных, так как каждый столбец имеет один элемент данных на строку) перестанавливаются в соответствии с правилом, определяемым связанной ЛКП. ЛКП, связанные с двумя различными строками, являются преимущественно различными, но могут быть в альтернативе одинаковыми. После перестановки всех строк данные считываются по столбцам для выдачи перемежающейся последовательности. Специалистам в данной области техники будет понятно что, перемежитель с длиной меньшей, чем 2^N и большей, чем 2^N-1 может быть сгенерирован удалением неправильных адресов из перемежителя длины 2^N.

В одном варианте осуществления изобретения 2-D перемежитель ЛКП включат следующие технические условия: размер перемежителя равен 32 (т.е. N=5), а массив данных определяется как {d(0), d(l), d(2),...d(31)}. Перемежитель организован как массив с четырьмя строками и восьмью элементами в строке. Элементы данных заполняются по строкам следующим образом;

Индексы строки в двоичном виде (00, 01, 10, 11) могут быть преимущественно инвентированы по битам (т.е. 00, 10, 01, 11), а строки переставлены таким образом, чтобы получить

Инвертирование бит служит для тасования строк перемежителя в соответствии с заданным алгоритмом инвертирования бит. Применение алгоритма инвертирования бит обеспечивает желаемое временное разделение между строками перемежителя. Тем не менее, инвертирование бит не обязательно для реализации перемежителя.

В конкретном варианте осуществления изобретения перестановка ЛКП генерируется в соответствии со следующими уравнениями:

x₁(n+1)=(5x₁(n)+7)_mod8, c x₁(0)=3,

x₂(n+1)=(x₂(n)+5)_mod8, c x₂(0)=0,

x₃(n+1)=(5x₃(n)+3)_mod8, c x₃(0)=4,

и

x₄(n+1)=(x₄(n)+3)_mod8, c x₄(0)=3,

Конфигурации перестановки задаются {3, 6, 5, 0, 7, 2, 1, 4}, {0, 5, 2, 7, 4, 1, 6, 3}, {4, 7, 6.1, 0, 3, 2, 5} и {7, 2, 5, 0, 3, 6, 1, 4} для четырех строк соответственно. Таким образом, после применения перестановки столбцов первая строка становится

(d(3) d(6) d(5) d(0) d(7) d(2) d(1) d(4)),

вторая строка становится

(d(16) d(21) d(18) d(23) d(20) d(17) d(22) d(19)),

третья строка становится

(d(120 d(15) d(14) d(9) d(8) d(11) d(10) d(13)),

и четвертая строка становится

(d(31) d(26) d(29) d(24) d(27) d(30) d(25) d(28)}

После того как все столбцы переставлены внутри соответствующих им строк, матрица перемежающихся данных имеет следующий вид:

Данные в перемежающейся матрице считываются по столбцам, выдавая следующую перемежающуюся последовательность:

{d(3), d(16), d(12), d(31), d(6), d(21), d(15), d(26), d(5), d(18), d(14),...,d(11),

d(30), d(1), d(22), d(10), d(25), d(4), d(19), d(13), d(28)}. Если требуется перемежитель длины 30, перемежитель, генерируемый, как описано выше, может быть укорочен удалением элементов данных d(30) и d(31), создавая следующую перемежающуюся последовательность:

{d(3), d(16), d(12), d(6), d(21), d(15), d(26), d(5), d(18), d(14),...,d(11), d(1), d(22), d(10), d(25), d(4), d(19), d(13), d(28)}.

ЛКП, используемые в конструкции перемежителя, могут быть сгенерированы либо в прямом, либо в обратном направлении, как требуется для оптимального использования с декодерами протокола MAP в турбодекодировании. В одном варианте осуществления изобретения генерирование обратной последовательности задается следующим уравнением:

x(n)=(ax (n+1)-c)_modМ,

где =(M^1/2)-1.

Следует заметить, что элемент , который используется в вышеприведенных уравнениях, представляет коэффициент "b", описанный в связи с вариантом осуществления изобретения по фиг.2.

Таким образом, генерирование последовательностей ЛКП требует, чтобы каждый перемежитель был однозначно определен параметрами 3R, где R число строк. Требуется относительно короткий умножитель log₂(C)хlog₂(С). Благодаря операции по модулю не требуется генерирование битов выше ячейки бит log₂(С). Для хранения промежуточных результатов R конгруэнтных последовательностей требуется одно множество R регистров.

Для каждой строки с различными параметрами x(0), "а" и "b" имеются многие различные возможности для перестановки последовательностей. Желательно выполнить исследование для оптимизации параметров перемежителя для использования с конкретными турбокодами.

На фиг.3 составной кодер 200, в соответствии с одним вариантом осуществления изобретения оптимизирован для конкретного турбокода, используемого в цифровых беспроводных коммуникационных системах МДКР (множественного доступа с кодовым разделением каналов). Кодер 200 содержит семь сумматоров 202, 204, 206, 208, 210, 212, 214 по модулю 2 и три ячейки 216, 218, 220 бит. Ячейки 216, 218, 220 бит могут быть реализованы как трехбитовый регистр или альтернативно три однобитовых регистра. Сумматоры 202, 204, 206, 208, 210, 212, 214 по модулю 2 соединяются с ячейками 216, 218, 220 бит точным способом так, чтобы создавать требуемое множество отводов обратной связи. Таким образом, сумматор 202 выполнен с возможностью приема входного бита. Сумматор 202 также соединяется с ячейкам 216 бит и с сумматорами 204 и 206. Ячейка 216 бит соединяется с ячейкой 218 бит и с сумматорами 204 и 206. Ячейка 218 бит соединяется с ячейкой 220 бит и с сумматорами 208 и 210. Сумматор 210 соединяется с сумматором 202. Сумматор 204 соединяется с сумматором 212. Сумматор 206 соединяется с сумматором 208. Сумматор 208 соединяется с сумматором 214. Ячейка 220 бит соединяется с сумматорами 210, 214 и 212. Сумматоры 212, 214 выполнен с возможностью вывода соответственно первого и второго символов.

В данной области техники известно, что эффективность ошибки может быть определена входным и выходным весовым коэффициентом событий ошибки в составных декодерах (не изображены). Смотри, например, S. Benedetto & G. Montorsi, Unveiling Turbo Codes: Some Results on Parallel Concatenated Coding Schemes, 42 IEEE Trans. Info. Theory 409-28 (март 1996). Входной весовой коэффициент события ошибки равен числу ошибок в битах, тогда как выходной весовой коэффициент события ошибки равен числу ошибок кодового символа. Событие ошибки входного весового коэффициента 1 очевидно будет отклоняться от состояния всех нулей и никогда повторно не объединится (1 будет циклически повторяться бесконечно в сдвиговом регистре, накапливая все больший выходной весовой коэффициент вдоль пути). Это происходит из-за рекурсивной, или обратной связи, части кодера. Благодаря этой структуре было показано, что эффективность турбокодов при высоком отношении сигнала к шуму (ОСШ) подавляется событиями выходной ошибки с входным весовым коэффициентом 2. Минимальный уровень ошибки турбокода может быть точно предсказан, используя, так называемую, асимптоту эффективного произвольного отклонения. Эффективное произвольное отклонение равно минимальному выходному весовому коэффициенту всех событий ошибки входного весового коэффициента 2. События ошибки входного весового коэффициента 2, которые являются короткими по длительности, будут обычно вызывать события ошибки минимального отклонения. Для кодера 200 фиг.3 полином обратной связи равен 1+D²+D³, а все возможные события ошибки входного весового коэффициента 2 представляются в виде D^k (1+D^7j), где j=1, 2,..., a k - произвольный сдвиг в диапазоне 0,..., K-7j (предполагается, что К является размером перемежителя). Это может быть легко проверено исследованием решеток составного кодера 200, что очевидно для специалистов в данной области техники.

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

Предположим, например, что конфигурация ошибки D^k (1+D⁷) вызывает событие ошибки минимального отклонения из первого декодера. Турбоперемежитель будет отображать две ошибки (D^k, D^k+7) в две позиции (Dⁿ, D^m). Если |m-n|=7 или равна некоторому числу, кратному 7, вероятным является событие ошибки малого отклонения из второго декодера. Основным назначением турбоперемежителя является не допускать появления таких отображений. А именно, перемежитель должен преимущественно отображать совокупности битов, которые склонны к событиям ошибки низкого весового коэффициента, в первом измерении, в совокупности битов, которые генерируют большую величину выходного весового коэффициента, во втором измерении. Таким образом, желаемым подходом к проектированию перемежителя является попытка не допустить отображения пар бит, расположенных в индексах (k, k+7j), в пары бит, расположеных в индексах (s, s+7t), с особым акцентом на меньшие значения j и t. Такие события входной ошибки перечислены в таблице 1. Для каждого события перечислен выходной весовой коэффициент контроля по четности первого составного кода, при использовании соответствующих конфигураций прокола для турбокодов прямой линии связи скорости 1/2, 1/3 и 1/4, как определено в IS-95.

Если данный перемежитель содержит отображение входного весового коэффициента 22 в виде D^k1(1+D⁷) D^k2(1+D⁷), тогда составной выходной весовой коэффициент события результирующей ошибки будет равен 2+3+3=8 для турбокода скорости 1/2. В предыдущем вычислении весовой коэффициент систематических битов (2) суммируется с соответствующим весовым коэффициентом проверки по четности из двух составных кодеров (3 и 3).

Аналогично, если перемежитель содержит отображение входного весового коэффициента 22 в виде D^k1(1+D⁷)D^k2(1+D¹⁴), тогда составной выходной весовой коэффициент события результирующей ошибки будет равен 2+3+6=11 для турбокода скорости 1/2 или 2+6+10=18 для турбокода скорости 1/3.

Кроме того, возможно, что события входной ошибки весового коэффициента 4 низкого составного выходного весового коэффициента могут отображаться в два события входной ошибки весового коэффициента 2 низкого выходного весового коэффициента во втором измерении. Такие отображения обозначаются 4{2,2}. Несмотря на то, что не имеется решения законченного вида для событий составной ошибки входного весового коэффициента 4, следующая таблица содержит некоторые из событий ошибки низкого выходного весового коэффициента для составного кодера 200, где составной кодер 200 используется как первый составной кодер для турбокодов прямой линии связи в цифровой беспроводной коммуникационной системе МДКР, использующей воздушный интерфейс, извлеченный из IS-95.

Если, например, перемежитель содержит отображение входного весового коэффициента 4{2,2) в виде D^k1(1+D³+D⁴+D⁵){D^k2(1+D⁷)D^k3(1+D⁷)}, тогда составной выходной весовой коэффициент события результирующей ошибки будет равен 4+2+3+3=12 для турбокода скорости 1/2. Это событие составной ошибки не значительно хуже, чем событие ошибки из-за отображения D^k1(1+D⁷)D^k2(+D¹⁴), которое имеет составной выходной весовой коэффициент 11. Первостепенной задачей проектирования, таким образом, является оптимизация параметров перемежителя так, что вышеописанные типы плохого отображения исключаются или, по меньшей мере, минимизируются. Идеально плохие отображения, имеющие самый низкий составной весовой коэффициент, являются отображениями, наиболее важными для исключения и/или минимизации. При проектированиии перемежителя для конкретного размера (например, 1530) возможно оптимизировать параметры премежителя так, чтобы минимизировать оба типа отображений (т.е. весового коэффициента 22 и весового коэффициента 4{2,2}). Этот подход выдает оптимальный перемежитель для этого конкретного размера. Следует заметить, что при проектировании перемежителя размера 2^N, который может быть надежно проколот до размера, большего, чем 2^N-1 (который называется перемежителем "дружелюбного прокола"), оптимизация для отображений 4{2,2} весового коэффициента может быть более трудной для достижения.

Было проведено исследование для получения перемежителей дружелюбного прокола размера 2^N из 2-D перемежителя ЛКП в соответствии с вариантом осуществления изобретения фиг.3. Таблица 3 содержит начальные результаты исследования.

Для каждого размера перемежителя число используемых строк и число используемых столбцов определяются вместе с коэффициентами x(0), “а” и “с”. Для простоты и эффективности в реализации тридцать две строки использовались для всех перемежителей.

В альтернативном варианте осуществления изобретения коэффициент а может быть установлен равным 1, причем было выполнено новое исследование для получения перемежителей "дружелюбного прокола" размера 2^N из 2-D перемежителя ЛКП. Уравнения прямой и обратной рекурсии ЛКП упрощаются, соответственно, в следующие:

X(n+1)=(x(n)+c)_modM

и

X(n)=(x(n+1)-c)_modM

Таблица 4 содержит начальные результаты исследования. Для простоты и эффективности реализации тридцать два ряда использовались для всех перемежителей. Специалистам в данной области техники будет понятно из результатов, изображенных в таблице 4, что установка "а" равным 1 во всех рекурсиях ЛКП не порождает ухудшения в качестве результирующих перемежителей. Кроме того, выигрыши сложности, достигаемые из упрощения установки "а" равным 1, являются существенными. Например, вторая и третья СТ, описанные в вариантах осуществления изобретения по фиг.2 (СТ, используемые для хранения значений а и a^b), не требуются. К-битовые умножители, описанные в варианте осуществления по фиг.2 являются также необязательными. Как видно из таблицы 4, только начальное условие х(-1) и аддитивная константа "с" должны быть определены для каждой строки перемежителя. Коэффициенты для перемежителей большего размера не включены в таблицу, которая определяет только результаты начального исследования, поскольку их не было в наличии ко времени регистраци настоящей заявки.

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

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

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

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

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

2. Турбокодер по п.1, отличающийся тем, что последовательность для тасования битов содержит рекурсию линейной конгруэнтной последовательности, генерируемую в соответствии со следующим уравнением:

х(n+1)=(ах(n)+c)mod М,

где n представляет временной индекс;

х(n) представляет индекс столбца при временном индексе n;

а, с и М - целые, М представляет период последовательности и удовлетворяются следующие условия: (i) с является взаимно простым для М, (ii) а-1 является кратным р, где р представляет любое простое число, которое делит М, (iii) когда М является кратным 4, а-1 должно быть кратно 4; (iv) x(0) - индекс столбца целого начального числа.

3. Турбокодер по п.2, отличающийся тем, что а=1.

4. Турбокодер по п.2, отличающийся тем, что период М является степенью 2.

5. Турбокодер по п.2, отличающийся тем, что x(0) равен 0 для каждой строки в перемежителе.

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

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

8. Турбокодер по п.1, отличающийся тем, что последовательность для тасования битов содержит рекурсию линейной конгруэнтной последовательности, генерируемую в соответствии со следующим уравнением:

х(n)=(a^((M/2)-1x(n+1)-c)mod М,

где n представляет временной индекс;

х(n) представляет индекс столбца при временном индексе n;

а, с и М - целые, М представляет период последовательности и удовлетворяются следующие условия: (i) с является взаимно простым для М, (ii) а-1 является кратным р, где р представляет любое простое число, которое делит М, (iii) когда М является кратным 4, а-1 должно быть кратно 4, (iv) x(0) - индекс столбца целого начального числа.

9. Турбокодер по п.8, отличающийся тем, что а=1.

10. Турбокодер по п.8, отличающийся тем, что период М является степенью 2.

11. Турбокодер по п.8, отличающийся тем, что x(0) равен 0 для каждой строки в перемежителе.

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

13. Устройство по п.12, отличающееся тем, что рекурсия линейной конгруэнтной последовательности генерируется в соответствии со следующим уравнением:

х(n+1)=(ах(n)+c)mod М,

где n представляет временной индекс;

х(n) представляет индекс столбца при временном индексе n;

а, с и М - целые, М представляет период последовательности и удовлетворяются следующие условия: (i) с является взаимно простым для М, (ii) а-1 является кратным р, где р представляет любое простое число, которое делит М, (iii) когда М является кратным 4, а-1 должно быть кратно 4; (iv) x(0) - индекс столбца целого начального числа.

14. Устройство по п.13, отличающееся тем, что а=1.

15. Устройство по п.13, отличающееся тем, что период М является степенью 2.

16. Устройство по п.13, отличающееся тем, что х(0) равен 0 для каждой строки.

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

18. Устройство по п.12, отличающееся тем, что рекурсия линейной конгруэнтной последовательности генерируется в соответствии со следующим уравнением:

х(n)=(a^((M/2)-¹⁾x(n+1)-c)mod М,

где n представляет временной индекс;

х(n) представляет индекс столбца при временном индексе n;

а, с и М - целые; М представляет период последовательности и удовлетворяются следующие условия: (i) с является взаимно простым для М, (ii) а-1 является кратным р, где р представляет любое простое число, которое делит М, (iii) когда М является кратным 4, а-1 должно быть кратно 4, (iv) x(0) - индекс столбца целого начального числа.

19. Устройство по п.18, отличающееся тем, что а=1.

20. Устройство по п.18, отличающееся тем, что период М является степенью 2.

21. Устройство по п.18, отличающееся тем, что x(0) равен 0 для каждой строки.

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

23. Перемежитель по п.22, отличающийся тем, что рекурсия линейной конгруэнтной последовательности генерируется в соответствии со следующим уравнением:

x(n+1)=(ах(n)+c)mod М,

где n представляет временной индекс;

х(n) представляет индекс столбца при временном индексе n;

а, с и М - целые; М представляет период последовательности и удовлетворяются следующие условия: (i) с является взаимно простым для М, (ii) а-1 является кратным р, где р представляет любое простое число, которое делит М, (iii) когда М является кратным 4, а-1 должно быть кратно 4, (iv) x(0) - индекс столбца целого начального числа.

24. Перемежитель по п.23, отличающийся тем, что а=1.

25. Перемежитель по п.23, отличающийся тем, что период М является степенью 2.

26. Перемежитель по п.23, отличающийся тем, что x(0) равен 0 для каждой строки в матрице ячеек хранения битов.

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

28. Перемежитель по п.22, отличающийся тем, что рекурсия линейной конгруэнтной последовательности генерируется в соответствии со следующим уравнением:

х(n)=(a^((M/2)-1⁾x(n+1)-c)mod M,

где n представляет временной индекс; х(n) представляет индекс столбца при временном индексе n;

а, с и М - целые; М представляет период последовательности и удовлетворяются следующие условия: (i) с является взаимно простым для М, (ii) а-1 является кратным р, где р представляет любое простое число, которое делит М, (iii) когда М является кратным 4, а-1 должно быть кратным 4, (iv) x(0) - индекс столбца целого начального числа.

29. Перемежитель по п.28, отличающийся тем, что а=1.

30. Перемежитель по п.28, отличающийся тем, что период М является степенью 2.

31. Перемежитель по п.28, отличающийся тем, что x(0) равен 0 для каждой строки в матрице ячеек хранения битов.

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3