Способ кодирования и декодирования данных для системы радиовещательной передачи цифровых сообщений

 

Изобретение относится к вычислительной технике и технике связи. Его использование в системах массового обслуживания позволяет передавать групповую и индивидуальную цифровую информацию больших объемов с высокой достоверностью по радиоканалу. Этот результат достигается благодаря тому, что применяемая кодовая конструкция позволяет активно бороться с одиночными ошибками и длинными пакетами ошибок. А также осуществлять кадровую синхронизацию. Комбинации K₁ символов остальных кодовых слов кадра используются для передачи индивидуального и/или группового адреса, необходимого для кодового разделения групп абонентов и соответствующего уникальному сочетанию локаторов позиций символов внешнего кода РС, применяемого для кодирования и декодирования информации, предназначенной определенной группе абонентов. 2 табл., 9 ил.

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

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

Известны системы кодирования и декодирования с исправлением ошибок, использующие сложные кодовые конструкции, такие коды-призведения двух линейных кодов с различными кодовыми расстояниями и сверткой части кодированной информации с третьим линейным кодом (патент ЕПВ N 0471085, кл. H 03 M 13/00, 1992), либо многоуровневое кодирование относительно слабым кодом с исправлением ошибок с последующим разделением избыточных символов на части и кодированием каждой из этих частей своим кодом с исправлением ошибок (патент ЕПВ N 0458468, кл. H 03 M 13/00, 1991). Все эти способы весьма сложны в реализации.

Наиболее близким к заявляемому является способ поблочной передачи слов цифровой информации (патент ЕПВ N 0204635, кл. H 03 M 13/00, 1986), включающий в себя на передающей стороне: - кодирование каждого передаваемого K-символьного слова внешним блоковым кодом (N, K), где N-K - число проверочных символов этого кода; - перемежение символов каждых W (W > 1) кодовых слов внешнего блокового кода (N, K); - кодирование перемеженных символов W кодовых слов внешнего блокового кода (N, K) внутренним кодом (n, k), где n-k - число проверочных символов этого кода; - формирование кодового кадра из кодовых слов внутреннего кода (n, k); - модуляцию сформированным кодовым кадром сигнала несущей частоты и передачу его по радиоканалу; на приемной стороне: - прием на каждом приемнике передаваемого сигнала, его демодуляцию и выделение синхропосылок; - декодирование кодовых слов внутреннего кода (n,k) с исправлением и/или обнаружением ошибок; - деперемежение декодированных символов W кодовых слов внешнего блокового кода (N,K);
- декодирование W кодовых слов внешнего блокового кода (N,K) с исправлением и/или обнаружением ошибок;
- выдачу декодированного сообщения получателю.

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

Для преодоления этого недостатка в способе кодирования и декодирования данных для системы радиовещательной передачи цифровых сообщений, включающем на передающей стороне:
- кодирование каждого передаваемого K-символьного слова внешним блоком кодом (N, K), где N-K - число проверочных символов этого кода;
- перемежение символов каждых W (W > 1) кодовых слов внешнего блокового кода (N, K);
- кодирование перемеженных символов W кодовых слов внешнего блокового кода (N, K) внутренним кодом (n, k), где n-k - число проверочных символов этого кода;
- формирование кодового кадра из кодовых слов внутреннего кода (n,k);
- модуляцию сформированным кодовым кадром сигнала несущей частоты и передачу его по радиоканалу;
на приемной стороне:
- прием на каждом приемнике передаваемого сигнала, его демодуляцию и выделение синхропосылок;
- декодирование кодовых слов внутреннего кода (n,k) с исправлением и/или обнаружением ошибок;
- деперемежение декодированных символов W кодовых слов внешнего блокового кода (N,K);
- декодирование W кодовых слов внешнего блокового кода (N,K) с исправлением и/или обнаружением ошибок;
- выдачу декодированного сообщения получателю,
на передающей стороне
- в качестве внешнего блокового кода (N,K) используют код (N,K) Рида-Соломона (PC) в поле GF(q) (q - алфавит кода), определенное сочетание наборов локаторов символьных позиций которого соответствует индивидуальным и/или групповым адресам приемников, которым предназначено данное информационное сообщение, при этом осуществляется несистематическое кодирование каждого передаваемого слова;
- при кодировании внутренним кодом (n,k) каждое полученное кодовое слово дополняют проверкой на четность;
- в качестве внутреннего кода (n,k) используют код (n, k+k₁) Боуза-Чоудхури-Хоквингема (БЧХ), k символами которого кодируют символы кода (N,K) PC, а k₁ символов кода (n, k+k₁) БЧХ соответствуют номеру смежного класса кода (n,k) БЧХ, вложенного в код (n,k+k₁) БЧХ;
- кодовый кадр формируют из N блоков по кодовых слов кода (n, k+k₁) БЧХ, причем в первых р (p<mN) кодовых словах кодового кадра упомянутые k₁ символов кода (n, k+k₁) БЧХ соответствуют порядковым номерам этих кодовых слов в кодовом кадре, а в остальных mN-p кодовых словах кодового кадра упомянутые k₁ символов кода (n, k+k₁) БЧХ соответствуют индивидуальным и/или групповым адресам приемников, которым предназначено данное информационное сообщение,
на приемной стороне:
- после демодуляции принятого сигнала находят кодовые слова кода (n, k+k₁) БЧХ с нулевыми синдромами;
- декодируют порядковые номера таких кодовых слов по k₁ символам кода (n, k+k₁) БЧХ, определяющим на передающей стороне номера смежных классов кода (n,k) БЧХ, вложенного в код (n,k+k₁) БЧХ;
- измеряют временные интервалы между такими кодовыми словами;
- сравнивают измеренные временные интервалы с заранее заданными интервалами между кодовыми словами с декодированными порядковыми номерами;
- при несоответствии измеренных временных интервалов заранее заданным повторяют на приемной стороне вышеперечисленные действия;
- при соответствии измеренных временных интервалов заранее заданным выделяют по кодовым словам с декодированными порядковыми номерами, используемым в качестве синхропосылки, начало данного кодового кадра, а также p первых кодовых слов данного кодового кадра;
- находят среди остальных mN-p кодовых слов данного кодового кадра кодовые слова кода (n, k+k₁) БЧХ с нулевыми синдромами;
- декодируют индивидуальный или групповой адрес приемника путем определения для таких кодовых слов номеров смежных классов кода (n, k) БЧХ, вложенного в код (n, k+k₁) БЧХ, по соответствующим k₁ символам этого кода в кодовых словах с нулевыми синдромами;
- сравнивают декодированный индивидуальный или групповой адрес приемника с набором адресов, доступных для данного приемника;
- при совпадении декодированного адреса приемника с одним из адресов такого набора декодируют в N блоках данного кодового кадра каждые m кодовых слов кода (n, k) БЧХ, вложенного в используемый на передающей стороне код (n, k+k₁) БЧХ, в смежных классах, номера которых определены для первых p кодовых слов в кодовом кадре их порядковыми номерами, а для остальных mN-p кодовых слов кодового кадра - декодированным адресом приемника;
- при деперемежении декодированных символов W кодовых слов внешнего кода (N, K) PC стирает те из них, для которых при декодировании кода (n, k) БЧХ получены отказы от декодирования;
- декодируют W кодовых слов внешнего кода (N, K) PC по нестертым позициям, используя то сочетание набора локаторов символьных позиций, которым соответствует декодированный индивидуальный или групповой код принятого сообщения, после чего и выдают декодированное информационное сообщение получателю.

Особенностью данного способа является то, что набор символов нестертых позиций для декодирования каждого из W кодовых слов внешнего кода (N, K) PC осуществляется по той группе из K позиций, символы которых были получены из слов БЧХ, принятых с меньшим количеством ошибок в слове.

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

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

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

На фиг. 1 показана организация группового кодирования для радиовещательной передачи цифровых сообщений; на фиг. 2 - структура кадров, из которых состоит пакет передаваемых сообщений; на фиг. 3 - способ формирования блоков кадра; на фиг. 4 - способ размещения кодовых слов в кадре, используемых для осуществления кадровой синхронизации; на фиг. 5 - способ формирования кодовых слов в кадре; на фиг. 6 - сдвиговый регистр для умножения принимаемой последовательности символов на проверочный многочлен кода (31, 16) БЧХ; на фиг. 7 - процесс поиска синхронизации по словам БЧХ (n, k+k₁), имеющим нулевые синдромы; на фиг. 8 - структурная схема устройства кодирования и передачи цифровой информации; на фиг. 9 - структурная схема устройства приема и декодирования цифровой информации.

Для повышения достоверности передачи информации по радиоканалу используется помехоустойчивое кодирование. Применяется каскадный код с внешним кодом Рида-Соломона (РС) и внутренним кодом Боуза-Чоудхури-Хоквингема (БЧХ), причем слова кода БЧХ обеспечивают кадровую синхронизацию. Применяемая кодовая конструкция позволяет активно бороться как с независимыми одиночными ошибками, так и с длинными пакетами ошибок и рэлеевскими замираниями.

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

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

Каждому индивидуальному или групповому адресу ставится в соответствие определенное сочетание набора локаторов позиций, используемого при кодировании символов информационного сообщения внешним кодом PC и представляющего собой некоторую порождающую матрицу из набора порождающих матриц соответствующих всевозможным индивидуальным или групповым адресам и определяющих вид передаваемой информации. Всего различных сочетаний наборов локаторов, а следовательно, и совокупности индивидуальных и групповых адресов в системе может быть до M = C^N_q, например, при использовании кода (96,48) PC в поле GF(2⁸), где N и q принимают соответственно значения 96 и 256, число адресов в системе может доходить до M = C⁹⁶₂₅₆= 10⁷³. В дальнейшей будем пользоваться только термином "групповой адрес", учитывая, что индивидуальным может быть любой групповой адрес, соответствующий единственному абоненту в данной группе.

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

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

Кадры пакета имеют одинаковую структуру (фиг. 2), каждая из которых состоит из N блоков. Каждый блок содержит m кодовых слов.

Кодирование символов информационного сообщения внешним кодом осуществляется следующим образом. Данные на передающей стороне разбиваются на порции по K · w · log₂q бит в каждой, где K и q - соответственно количество информационных символов и алфавит внешнего кода PC кодовой конструкции, используемой для формирования одного кадра. Каждые K информационных символов из W групп кодируются внешним кодом (N, K) PC, причем сочетание набора локаторов позиций в порождающей матрице соответствует определенному групповому адресу абонентов, которым предназначена данная информация.

Применяемый для кодирования код PC используется в несистематическом виде, и алгоритм кодирования заключается в перемножении информационного вектора а = (A₀, A₁,..., А_K-1), содержащего K информационных символов, на порождающую матрицу G, элементами которой являются степени локаторов позиций Z₀, Z₁, ..., Z_N-1:
(A₀, A₁, ..., A_K-1) · G = (U₀, U₁, ..., U_N-1), (1)
где

Z₀, Z₁, ..., Z_N-1 - различные ненулевые элементы поля GF(q);
U₀ , U₁, ..., U_N-1 - символы кодового слова.

Порождающая матрица G из (1) делится на две G₁ и G₂ по одинаковому количеству K локаторов в каждой, и для нахождения символов кодового слова u = (U₀, U₁, ..., U_N-1), разделенных на две равные группы, составляющие вектора u₁ = (U₀, U₁, ..., U_K-1) и u₂ = (U_K, U_K+1, ..., U_N-1), информационный вектор а умножается на эти две матрицы G₁ и G₂, что эквивалентно умножению на матрицу G:
a·G₁=u₁, a·G₂=u₂, (2)
где


Каждая из этих матриц G₁ и G₂ содержит степени K локаторов позиций символов кодового слова.

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

Каждая группа символов разбивается на m частей, каждая из которых используется для формирования m кодовых слов одного из блоков. На фиг. 3 показан способ использования символов групп из табл. 1 для формирования кодовых слов каждого из N блоков кадра. В качестве примера на фиг. 3 для формирования каждого кодового слова кадра берутся два символа внешнего кода PC.

Кодовые слова блоков получают кодированием одного или нескольких символов внешнего кода PC внутренним кодом БЧХ, позволяющим исправлять и обнаруживать несколько ошибок в слове.

В качестве внутреннего кода используется двоичный код БЧХ с блоковой длиной n, исправляющий t ошибок, который строится как циклический код, порождающий многочлен которого равен произведению различных минимальных многочленов для элементов α, α², ..., α^2t.
Для осуществления кадровой синхронизации применяется код (n,k+k₁) БЧХ, где k информационных символов представляют собой символы внешнего кода PC, а k₁ символов несут в себе информацию о порядковом номере кодового слова в кадре, причем кодом (n,k+k₁) кодируются первые p=qm+r кодовых слов кадра, занимающие в общем случае целиком q блоков и часть q+1 блока (фиг. 4). Остальные кодовые слова блоков кадра получают кодированием символов внешнего кода PC кодом БЧХ (n,k+k₁), где k₁ символов используются для задания группового адреса.

В качестве примера рассмотрим код БЧХ с n=31, k=16 и g(x)= M¹(x)·M³(x)·M⁵(x), где M¹(x)=1+x²+x⁵, M³(x)=1+x²+x³+x⁴+x⁵, M⁵(x)= 1+x+x²+x⁴+x⁵ минимальные многочлены соответственно для элементов α, α³, α⁵. Тогда синдромы S₁, S₃, S₅ могут быть получены из следующих соотношений:

где
r¹(x) - остаток от деления принятого кодового слова, записанного в виде полинома n-1 степени c(x) на минимальный многочлен M¹(x), соответствующий одному из элементов α, α³, α⁵; r¹(x)=c(x)mod M¹(x), r³(x)=c(x)mod M³(x), r⁵(x)=c(x)mod M⁵(x).

На передающей стороне для кодирования используется код БЧХ (31, 21), в который вложено 32 кода (31, 16), номера смежных классов которого используются как для передачи порядковых номеров кодовых слов в кадре, так и для передачи группового адреса, и определяются дополнительными информационными символами k₁= 5 в коде (31, 21), k=16 информационных символов которого используются для кодирования двух восьмиразрядных символов внешнего кода. Причем кодирование кодом (31, 21) осуществляется таким образом, что лидеры смежных классов, определяющие номера смежных классов кода (31, 16), находятся по синдромам S₁ из (3).

Первые p=30 кодовых слов кадра (фиг. 5) формируются путем прибавления к словам кода (31, 16) БЧХ d₁, d₂, ...d₃₀ соответственно лидеров смежных классов v₁, v₂, ...v₃₀, и таким образом полученные слова кода БЧХ (31, 21) c₁= d₁+v₁, c₁=d₁+v₁,...c₁=d₁+v₁, дополненные проверкой на четность и имеющие в результате длину n'=32 символа, используются как p первых кодовых слов кадра, в рассмотренном выше формате сообщений. Причем каждому лидеру смежного класса v₁, v₂,...v₃₀ ставится в соответствии порядковый номер кодового слова в кадре, т.е. v₁ соответствует первому кодовому слову, v₂ - второму кодовому слову в кадре и т.д.

Лидеры смежных классов v₀ и v₃₀ используются для кодирования остальных mN-p кодовых слов кадра, несущих в себе информацию о групповом адресе передаваемого сообщения. Для этого mN-p кодовых слов разбиваются на группы по γ слов в каждой. Количество таких групп в кадре определяется целым числом от деления (mN-p) на γ, т.е. На фиг. 5 показан пример кодирования группы из γ = 8 кодовых слов групповым адресом, представленным в виде двоичного вектора i_J= (I₀, I₁,...I₇), где I₀=1, I₁=0, I₂=1, I₃=1, I₄=0, I₅=1, I₆= 1, I₇=0. Кодирование заключается в прибавлении к слову БЧХ (31, 16) одного из лидеров смежных классов v₀ или v₃₁, которым ставится в соответствие информационный символ вектора группового адреса 1 или 0. Полученные таким образом слова кода БЧХ дополняются проверками на четность до длины n'=n+1 и используются для передачи в кадре вслед за первыми p кодовыми словами кадра. Таким образом, при передаче группового или индивидуального адреса используется код с повторениями.

Оставшиеся кодовых слов кадра формируются путем кодирования символов внешнего кода PC кодом (31, 16) БЧХ с последующим дополнением каждого проверкой на четность, и используются при передаче в качестве последних кодовых слов кадра.

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

На приемной стороне каждым абонентским приемником принятый сигнал демодулируется и затем осуществляется поиск кадровой синхронизации, который заключается в нахождении точек синхронизации по нулевым значениям синдрома принимаемых слов кода (n,k+k₁) БЧХ и сравнении физически измеренных временных интервалов между точками синхронизации с вычисленными временными интервалами. Нахождение синдромов осуществляется путем умножения принятых символов на проверочную матрицу, что равносильно вычислениям по формулам (3). Так как применяется циклический код БЧХ, данная процедура может быть реализована с помощью сдвигового регистра, связи которого задают коэффициенты при степенях проверочного многочлена h(x). Например, для рассмотренного (31, 16) БЧХ кода с приведенным ранее порождающим полиномом g(x) = M¹(x)·M³(x)·M⁵(x) проверочный многочлен будет
h(x) = (1+x)(1+x³+x⁵)(1+x+x³+x⁴ +x⁵)(1+x+x²+x³+x⁵)= x¹⁶+x¹² x¹¹+x¹⁰+x⁹+x⁴+x+1
и сдвиговый регистр будет иметь вид, показанный на фиг. 6. В сдвиговом регистре осуществляется перемножение на порождающий многочлен последовательности демодулированных символов, поступающих из канала связи на вход данного регистра. Фиксация точки синхронизации происходит по десяти друг за другом следующим нулям в регистре сдвига, соответствующим нулевым синдромам S₃ и S₅. Комбинация символов в сдвиговом регистре, соответствующих S₁, будет определять один из тридцати лидеров смежного класса c v₁ по v₃₀. Каждому их этих лидеров при кодировании ставился в соответствие номер кодового слова в кадре, и, следовательно, вычислив S₁ с учетом S₃=S₅=0, можно определить порядковый номер этого кодового слова в кадре.

Для первого принятого слова кода БЧХ, у которого S₃=S₅=0, по синдрому S₁ определяется порядковый номер данного кодового слова в кадре и измеряется временной интервал до прихода следующего кодового слова с некоторым порядковым номером m₂ в кадре, имеющего нулевые синдромы S₃ и S₅, путем подсчета принятых символов между этими кодовыми словами кадра (фиг. 7). Затем происходит сравнение количества этих подсчитанных символов с количеством символов, составляющих кодовые слова, стоящие между кодовыми словами с номерами m₁ и m₂ в кадре, т.е. определяется, выполняется ли следующее равенство:

где
n₀₁ - количество принятых символов между кодовыми словами с порядковыми номерами в кадре m₁ и m₂;
n' - количество символов в одном кодовом слове.

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

Если же равенство (4) не выполняется, то находится следующее кодовое слово для которого S₃=S₅=0 с порядковым номером m₃ в кадре и проводятся аналогичные вычисления точек синхронизации относительно этого вновь полученного слова с порядковым номером m₃, используя два уравнения типа (4):

Если установление синхронизации по этим двум парам точек не произошло, то ищется четвертое слово с порядковым номером слова в кадре m₄, и в случае отрицательного результата поиск точек синхронизации продолжается по следующим кодовым словам с номерами m₅, m₆ и т.д. В случае заполнения списка номеров принятых кодовых слов с m₁ по m₈ для каждого вновь принятого кодового слова с нулевыми синдромами S₃ и S₅ список сдвигается, вытесняя номер наиболее давнего принятого слова, которое при поиске точек синхронизации не рассматривается, при этом решается 7 уравнений типа (4):

Необходимо отметить, что во время поиска точек синхронизации одновременно с подачей символов в сдвиговый регистр для вычисления синдромов осуществляется накопление символов в буфере типа регистра сдвига длиной n'·p для того, чтобы в случае установления синхронизации по двум последним p-1 и p или близким к последним кодовым словам, используемым для осуществления кадровой синхронизации, можно было восстановить информацию из всех ранее переданных p кодовых слов кадра.

После установления кадровой синхронизации принимаются все N блоков кодовых слов кадра. Из mN-p кодовых слов, следующих за первыми p кодовыми словами кадра, выделяется групповой адрес, декодирование которого осуществляется следующим образом. Согласно фиг.5 для кодирования группового адреса применяется код с повторениями, где каждое слово, содержащее групповой адрес, состоит из γ двоичных символов, а каждый символ передается одним из смежных классов кода (n, k) БЧХ.

Рассмотрим алгоритм декодирования группового адреса на примере формата передаваемого кадра с n = 96, m = 4, p = 30, в котором групповой адрес передается словами кода БЧХ, составляющими группы по γ слов в каждой. Число таких групп в кадре будет равно целому числу, полученному в результате деления (mN-p) кодовых слов кадра на длину γ вектора группового адреса, и для рассматриваемого примера будет [(4 · 96 - 30)/8)] = 44. Для всех этих 44 кодовых слов кадра находятся синдромы S₃ и S₅ и составляется список из 44-х векторов, каждый из которых представляет собой оценку группового адреса (табл.2). Причем если синдромы S₃ и S₅ принятого слова равны нулю, то по синдрому S₁ определяется лидер смежного класса, и если это лидеры v₀ или v₃₁, то принимается решение, что передавался соответственно символ 1 или 0, если же это лидер какой-либо из v₁, v₂, ..., v₃₀, то данный символ объявляется стертым. В табл.2 стертые символы отмечены знаком *. Для символов группового кода, переданных словами кода БЧХ, посчитанные синдромы S₃ и S₅ которых отличны от нуля, принимается решение о стирании.

Каждому из 44 оценочных векторов в табл.2 присваивается надежность, т.е. величина, зависящая от количества стертых позиций в этом векторе. Максимальная надежность для вектора, не имеющего ни одного стирания, - 8 и минимальная для вектора, имеющего одни стирания, будет 0. Для определения значения передаваемого символа вектора группового адреса надежности для каждого символа суммируются, причем надежности, соответствующие символу 0, прибавляются, а надежности, соответствующие символу 1, вычитаются. По знаку суммы Σ_i надежностей выносится решение о значении принятого в данной позиции символа. В табл.2 показан пример искажения символов адресного кода при передаче в канале с ошибками и стираниями, и по шести первым векторам дается оценка передаваемого группового адреса:

В реальном случае оценка должна даваться по всем векторам, а для рассматриваемого примера по - 44 векторам.

После нахождения группового адреса осуществляется декодирование всех Nm кодовых слов кадра, представляющих собой слова кода (n, k+k₁) БЧХ, причем декодирование осуществляется в смежных классах кода (n, k) БЧХ, при котором реализуется конструктивное расстояние кода (n, k) БЧХ. Для этого к каждому из первых p слов кода БЧХ прибавляются соответственно лидеры смежных классов с v₁, v₂, ..., v₃₀, а к остальным mN-p кодовым словам, составляющим группы по γ кодовых слов, прибавляются соответственно лидеры смежных классов v₀ или v₃₁ в зависимости от символов вектора уже декодированного группового адреса.

Затем декодирование (n, k) БЧХ кода с исправлением ошибок может осуществляться традиционными методами (Берлекэмп Э. Алгебраическая теория кодирования. - М. : Мир, 1971, с.186 - 208). Так как каждое слово кода БЧХ дополнено проверкой на четность, при декодировании с исправлением и обнаружением ошибок происходит обнаружение ошибок более высокой кратности.

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

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

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

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

Так как информационный вектор a можно получить по любым K позициям кода PC, то при декодировании для восстановления информационных символов вектора a достаточно умножить вектор кодового слова u на любую из матриц G^-₁¹ или G^-₂¹ соответственно, обратных матрицам G₁ и G₂ из (2):
a = u₁·G^-₁¹ или (5)
a = u₂·G^-₂¹ (6)
При этом декодирование осуществляется по символам того вектора u₁ или u₂, который имеет наименьшее число стертых позиций, а эти стертые позиции вычисляются по нестертым позициям второго вектора.

Нахождение символов вектора u₁ через символы вектора u₂ и обратное преобразование осуществляется согласно формулам:
u₁= u₂·G^-₂¹·G₁= u₂·C, (7)
где
C = (G^-₂¹·G₁)^T;

где
G = (G^-₁¹·G₂)^T.
Выражения (7) и (8) можно представить соответственно в виде систем линейных уравнений:

где
U_j - символы вектора u₁;
U_i - символы вектора u₂;
c_ij - элементы матрицы C;

где
U_j - символы вектора u₂;
U_i - символы вектора u₁;
b_ij - элементы матрицы B.

Пусть в кодовом слове стерто l = l₁ + l₂ позиций из N при N ≅N - K, l₁ и l₂ из которых распределены соответственно в u₁ и u₂. Тогда выбирается наименьшее из l₁ и l₂ число стертых позиций в векторах u₁ и u₂ и вычисляются значения, соответствующие этим стертым позициям, по нестертым позициям второго вектора, используя формулы (9), (10). Пусть Г₁ и Г₂ - множества номеров нестертых позиций K-l₁ и K-l₂ соответственно для векторов u₁ и u₂, а J₁ и J₂ - множества номеров стертых позиций l₁ и l₂ соответственно для векторов u₁ и u₂, и пусть l₁ ≅ l₂. Тогда находим группу, состоящую из l₁ стертых позиций вектора u₁, представляющую собой некоторый вектор u_с, по любым l₁ из K-l₂ нестертых позиций вектора u₂ согласно системе линейных уравнений (10):

Суммы по подмножеству нестертых символов Г₁ переносятся в правую часть системы уравнений и вычитаются из соответствующих символов u_j, образуя элементы λ_j :

где

Полученная система (12) решается относительно символов U_i, i ∈ J₁ вектора u_c, для чего обращается квадратная l₁ · l₁ матрица B₁, состоящая из элементов b_ij, где i ∈ J₁ и j ∈ Г₂ :
u_c= Λ·B^-₁¹ (13)
где
u_c - вектор, состоящий из символов U₁, соответствующих стертым позициям;
Λ - вектор, состоящий из l₁ элементов λ_j, j ∈ Г₂.
Следовательно, для нахождения l₁ значений стертых позиций вектора u₁ по нестертым позициям вектора u₂ требуется обращение матрицы размерности l₁ · l₁ и умножение ее на вектор длиной l₁.

Например, при использовании кода (96, 48) PC и стертых l = 5 позициях в полученном из канала связи кодовом слое u = (U₀, U₁, ..., U_N-1), причем l₁ = 2 и l₂ = 3 стертых позиций распределены соответственно в u₁ = (U₀, U₁, ..., U_K-1) и u₂ = (U_K, U_K+1, ..., U_n-1), при множествах стертых позиций J₁= {ζ1, ζ2} и J₂= {φ1, φ2, φ3} соответственно для векторов u₁ и u₂, находится вектор u_c= (U_ζ1, U_ζ2), состоящий из значений стертых позиций, которыми необходимо дополнить вектор u₁, чтобы затем использовать выражение (5) для восстановления информационного вектора a. Согласно формуле (11) получаем систему уравнений:

Затем выражение (12) для данного случая примет вид:

где


Согласно (13) получаем:
u_c= Λ·B^-₁¹,
где
u_c= (U_ζ1, U_ζ2);


Для нахождения вектора u_c в данном случае при стираниях l₁=2 требуется обращение матрицы B₁ размерности 2·2.

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

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

На приемной стороне реализация рассмотренного способа может быть осуществлена с помощью устройства, структурная схема которого представлена на фиг. 9. Это устройство содержит приемник 9, вход которого соединен с линией 8 связи, блок 10 синхронизации, блок 11 памяти, декодер 12 группового адреса, декодер 13 внутреннего кода, блок 14 деперемежения, декодер 15 внешнего кода, блок 16 отображения цифровой информации. Выход приемника 9 соединен с первым входом блока 11 памяти и со входом блока 10 синхронизации, выход которого подключен к первому входу декодера 13 внутреннего кода и входу декодера 12 группового адреса, выход которого соединен с первым входом декодера 15 внешнего кода и со вторым входом декодера 13 внутреннего кода, выход которого подключен ко второму входу декодера 15 внешнего кода через блок 14 деперемежения. Выход декодера 15 внешнего кода подсоединен ко входу блока 16 отображения цифровой информации.

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

Блок 2 памяти представляет собой определенную область памяти для хранения всевозможных порождающих матриц G, и может быть реализован на микросхемах ОЗУ или ПЗУ общего применения при аппаратной реализации либо отведением необходимого объема памяти при программной реализации.

Кодер 3 внешнего кода, декодер 15 внешнего кода и декодер 12 группового адреса, алгоритмы которых детально описаны в заявляемом способе, могут быть реализованы программно как на языках высокого уровня (Паскаль, Си), так и микропрограммно, например на однокристалльной микро-ЭВМ КР1830ВЕ51.

Блоки 4 и 14 перемежения и депережежения могут быть реализованы согласно описанию периодических устройств перемежения в (Кларк Дж., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи. - М.: Радио и связь, 1987, с.324-327).

Кодер 5 и декодер 13 внутреннего кода могут быть реализованы согласно схемам приведенным в (Берлекэмп Э. Алгебраическая теория кодирования. - М.: Мир, 1971) соответственно на с. 138, 141 и с.145-147.

В качестве передатчика 6 и приемника 9 могут быть использованы кварцованные соответственно передатчик и гетеродинный приемник для работы в УКВ ЧМ диапазоне частот.

Блок 10 синхронизации содержит сдвиговый регистр, приведенный на фиг. 6, дополненный комбинационной логической схемой по вычислению синдомов, аналогичной приведенной в (Берлекэмп Э. Алгебраическая теория кодирования. - М.: Мир, 1971, с.136), а также несколько счетчиков, обеспечивающих подсчет пришедших символов из канала между словами БЧХ, имеющими нулевые синдромы. Сравнительно несложная техническая реализация этого блока может быть осуществлена как программно, так и на микросхемах общего применения или специализированной БИС, например на базовом матричном кристалле 1515ХМ1.

Блок 16 отображения цифровой информации может представлять собой какой-либо дисплей, например монитор ПЭВМ, позволяющий просматривать принятую информацию получателю сообщений.

Устройство кодирования и передачи цифровой информации работает следующим образом. По телефонной линии 7 связи (фиг. 8) от различных отправителей формирователь 1 информационных сообщений посредством телефонного модема получает информационные сообщения, сопровождаемые групповыми адресами, с помощью которых отправитель определяет ту группу получателей, которой он хочет передать данную информацию. Формирователь 1 информационных сообщений выстраивает полученные сообщения в очередь, нарезая каждое из них на последовательности по K символов, имеющих размерность log₂q двоичных разрядов, и передает эти последовательности в кодер 3 внешнего кода с одновременной выдачей группового адреса, соответствующего данному сообщению, в блок 2 памяти и кодер 5 внутреннего кода. Блок 2 памяти осуществляет доступ кодеру 3 внешнего кода к записанным в нем локаторам некоторой порождающей матрицы соответствующей некоторому групповому адресу i_j передаваемого сообщения. Совокупность локаторов этой порождающей матрицы используется кодером 3 для кодирования внешним кодом PC данных K информационных символов. Затем в блоке 4 перемежения накапливаются W кодовых слов кода PC с последующим перемежением их символов. В кодере 5 внутреннего кода перемеженные символы внешнего кода PC кодируются внутренним кодом БЧХ, при этом образуются блоки из m кодовых слов (фиг. 3). Причем первые p кодовых слов кадра дополняются информацией о порядковом номере этих слов в кадре (фиг. 5), а остальные кодовые слова кадра дополняются информацией о групповом адресе передаваемого сообщения, который подается на кодер 5 внутреннего кода с формирователя 1 информационных сообщений. После этого символы кодовых слов блоков кадра поступают в передатчик 6, где осуществляется модуляция ими сигнала несущей частоты, который передается в линию 8 связи.

В качестве линии 8 связи может использоваться один или несколько радиоканалов в УКВ-диапазоне частот.

Устройство приема и декодирования цифровой информации работает следующим образом. Приемником 9 (фиг. 9) из линии 8 связи принимается сигнал несущей частоты, демодулируется и поступает на блок 10 синхронизации, где осуществляется поиск кадровой синхронизации, и на блок 11 памяти, на который в случае нахождения точек синхронизации с блока 10 синхронизации подается управляющий сигнал, по которому блоком 11 памяти осуществляется запись всех кодовых слов кадра. Декодером 12 группового адреса из кодовых слов, хранящихся в блоке 11 памяти, выделяется групповой адрес принятого сообщения и сравнивается с набором групповых адресов i₁,....i_y, соответствующих некоторым матрицам, обратным порождающим которые имеются у данного абонентского приемника для декодирования и получения информации из принятых сообщений, предназначенных для данного абонента. Если групповой адрес i_j принятого сообщения не совпадает ни с одним из имеющегося набора адресов i_i,...,i_y, то происходит отказ от декодирования кодовых слов принятого кадра. В противном случае декодером 13 внутреннего кода осуществляется декодирование кодовых слов кадра, хранящихся в блоке 11 памяти, и передача массива символов внешнего кода в блок 14 деперемежения. После деперемежения символы, составляющие слова внешнего кода PC, декодируются в декодере 15 внешнего кода с использованием той обратной матрицы , которая соответствует групповому адресу i_j, поступающему на этот декодер 15 внешнего кода из декодера 12 группового адреса. В результате декодирования каждого слова внешнего кода PC из W, переданных в кадре, восстанавливается информация переданного сообщения, которая в блоке 16 отображения информации индицируется получателю данного сообщения.

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

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

Способ кодирования и декодирования данных для системы радиовещательной передачи цифровых сообщений, включающий на передающей стороне кодирование каждого передаваемого K-символьного слова внешним блоковым кодом (N, K), где N - K - число проверочных символов этого кода, перемежение символов каждых W (W > 1) кодовых слов внешнего блокового кода (N, K), кодирование перемеженных символов W кодовых слов внешнего блокового кода (N, K) внутренним кодом (n, k), где n - k - число проверочных символов этого кода, формирование кодового кадра из кодовых слов внутреннего кода (n, k), модуляцию сформированным кодовым кадром сигнала несущей частоты и передачу его по радиоканалу, на приемной стороне - прием на каждом приемнике передаваемого сигнала, его демодуляцию и выделение синхропосылок, декодирование кодовых слов внутреннего кода (n, k) с исправлением и/или обнаружением ошибок, деперемежение декодированных символов W кодовых слов внешнего блокового кода (N, K), декодирование W кодовых слов внешнего блокового кода (N, K) с исправлением и/или обнаружением ошибок, выдачу декодированного сообщения получателю, отличающийся тем, что на передающей стороне в качестве внешнего блокового кода (N, K) используют код (N, K) Рида-Соломона (РС) в поле GF(q) (q - алфавит кода), определенное сочетание наборов локаторов символьных позиций которого соответствует индивидуальным и/или групповым адресам приемников, которым предназначено данное информационное сообщение, при этом осуществляется несистематическое кодирование каждого передаваемого слова, при кодировании внутренним кодом (n, k) каждое полученное кодовое слово дополняют проверкой на четность, в качестве внутреннего кода (n, k) используют код (n, k + k₁) Боуза - Чоудхури - Хоквингема (БЧХ), k символами которого кодируют символы кода (N, K) РС, а k₁ символов кода (n, k + k₁) БЧХ соответствуют номеру смежного класса кода (n, k) БЧХ, вложенного в код (n, k + k₁) БЧХ, кодовый кадр формируют из N блоков по m = w log₂ q/k кодовых слов кода (n, k + k₁) БЧХ, причем в первых p(p < mN) кодовых словах кодового кадра упомянутые k₁ символов кода (n, k + k₁) БЧХ соответствуют порядковым номерам этих кодовых слов в кодовом кадре, а в остальных mN - p кодовых словах кодового кадра упомянутые k₁ символов кода (n, k + k₁) БЧХ соответствуют индивидуальным и/или групповым адресам приемников, которым предназначено данное информационное сообщение, на приемной стороне после демодуляции принятого сигнала находят кодовые слова кода (n, k + k₁) БЧХ с нулевыми синдромами, декодируют порядковые номера таких кодовых слов по k₁ символам кода (n, k + k₁) БЧХ, определяющим на передающей стороне номера смежных классов кода (n, k) БЧХ, вложенного в код (n, k + k₁) БЧХ, измеряют временные интервалы между такими кодовыми словами, сравнивают измеренные временные интервалы с заранее заданными интервалами между кодовыми словами с декодированными порядковыми номерами, при несоответствии измеренных временных интервалов заранее заданным повторяют на приемной стороне указанные действия, при соответствии измеренных временных интервалов заранее заданным выделяют по кодовым словам с декодированными порядковыми номерами, используемым в качестве синхропосылки, начало данного кодового кадра, а также p первых кодовых слов данного кодового кадра, находят среди остальных mN - p кодовых слов данного кодового кадра кодовые слова кода (n, k + k₁) БЧХ с нулевыми синдромами, декодируют индивидуальный или групповой адрес приемника путем определения для таких кодовых слов номеров смежных классов кода (n, k) БЧХ, вложенного в код (n, k + k₁) БЧХ, по соответствующим k₁ символам этого кода в кодовых словах с нулевыми синдромами, сравнивают декодированный индивидуальный или групповой адрес приемника с набором адресов, доступных для данного приемника, при совпадении декодированного адреса приемника с одним из адресов такого набора декодируют в N блоках данного кодового кадра каждые m кодовых слов кода (n, k) БЧХ, вложенного в используемый на передающей стороне код (n, k + k₁) БЧХ, в смежных классах, номера которых определены для первых p кодовых слов в кодовом кадре их порядковыми номерами, а для остальных mN - p кодовых слов кодового кадра - декодированным адресом приемника, при деперемежении декодированных символов W кодовых слов внешнего кода (N, K) РС стирают те из них, для которых при декодировании кода (n, k) БЧХ получены отказы от декодирования, декодируют W кодовых слов внешнего кода (N, K) РС по нестертым позициям, используя то сочетание набора локаторов символьных позиций, которым соответствует декодированный индивидуальный или групповой код принятого сообщения, после чего выделяют декодированное информационное сообщение получателю.

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4, Рисунок 5, Рисунок 6, Рисунок 7, Рисунок 8, Рисунок 9, Рисунок 10

PC4A - Регистрация договора об уступке патента Российской Федерации на изобретение

Номер и год публикации бюллетеня: 6-1999

(73) Патентообладатель:
ЗАО "РАДИОТЕКСТ"

Договор № 7495 зарегистрирован 17.07.1998

Извещение опубликовано: 27.02.1999