СПОСОБ КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ СООБЩЕНИЙ Российский патент 2017 года по МПК H03M13/00 

ОБЛАСТЬ ТЕХНИКИ

[0001] Данное техническое решение относится к системе связи с передачей пакетов данных и более конкретно к способам помехоустойчивого кодирования и декодирования информации.

УРОВЕНЬ ТЕХНИКИ

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

[0003] Коды с малой плотностью проверок на четность представляют большой интерес как с теоретической, так и с практической точки зрения, различные варианты LDPC кодов используются в таких системах и стандартах радиосвязи, как DVB-S2, 10GBase-T, WiFi 802.11 и др.

[0004] В данном уровне техники известен класс низкоплотностных кодов, называемых ZigZag коды. Этот класс кодов представляет интерес из-за сравнительно простого алгоритма декодирования, при этом сохраняя достаточно хорошее качество исправления ошибок в различных условиях (в пределах 1.5 дБ от предела Шеннона).

[0005] Из уровня техники известен патент ЕР 1432129 А2 «Iterative Decoding of parallel concatenated Zigzag codes», патентообладатель: Nokia Corporation, опубликовано: 23.06.2004. Итерационный декодер, использующий параллельный каскадный ZigZag код, содержащий схему данных для использования внешней информации во время итеративного декодирования, в которой обновляют проверочную информацию для битов четности во время итераций.

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

СУЩНОСТЬ ИЗОБРЕТЕНИЯ

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

[0008] Техническим результатом данного технического решения является повышение помехозащищенности передачи информации.

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

[00010] В некоторых вариантах осуществления технического решения помехоустойчивым кодом является ZigZag код с кодовой скоростью 1/3.

[00011] В некоторых вариантах осуществления технического решения при распределении проверочных бит по группам, в случае двух групп в первую группу попадают нечетные биты, а во вторую - четные.

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

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

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

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

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

[00017] В некоторых вариантах осуществления технического решения при совместном декодировании метрики соответствующие всем битам в исходных сообщениях, складываются.

[00018] В некоторых вариантах осуществления технического решения передача сообщений на различных частотах происходит с перерывом по времени.

КРАТКОЕ ОПИСАНИЕ ЧЕРТЕЖЕЙ

[00019] Признаки и преимущества настоящего технического решения станут очевидными из приводимого ниже подробного описания изобретения и прилагаемых чертежей, на которых:

[00020] На Фиг. 1 - вероятность битовой ошибки для кодирования помехоустойчивым ZigZag с кодовыми скоростями 1/2 и 1/3 в канале с нормальным шумом;

[00021] На Фиг. 2 - пример реализации схемы распределения информационных и проверочных бит по сообщениям;

[00022] На Фиг. 3 - блок-схема способа кодирования и декодирования сообщений.

ПОДРОБНОЕ ОПИСАНИЕ ИЗОБРЕТЕНИЯ

[00023] Ниже будут описаны понятия и определения терминологии, необходимые для подробного раскрытия осуществляемого изобретения.

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

[00025] Информационный бит - бит, вырабатываемый источником данных и предназначенный для передачи данных пользователя [из п. 57 ГОСТ 24402-88].

[00026] Проверочный бит - бит, предназначенный для обнаружения ошибок в знаке данных или блоке данных [из п. 57 ГОСТ 24402-88].

[00027] Кодовая скорость - отношение длины кодового блока на входе к длине преобразованного кодового блока на выходе кодера.

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

[00029] ZigZag код - в теории кодирования это линейный код с исправлением ошибок, в котором разделяют входные данные на сегменты фиксированного размера и добавляют последовательность проверочных битов, где каждый проверочный бит является исключительным в сегменте.

[00030] Предел Шеннона - предельная (максимальной) скорость передачи информации (пропускная способность) в зашумленном канале связи.

[00031] Передатчик - устройство, которое получает информационные биты от их источника, например от счетчика, осуществляет их кодирование, формирование пакетов данных, добавляет служебную информацию и передает в эфир несколько раз на различных частотах с модуляцией DBPSK.

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

[00033] Метрика - числовой показатель вероятности того, что принято значение бит «1». Как правило, отрицательное значение метрики соответствует принятому значению «1», а положительное - «0». Чем больше метрика по модулю, тем больше уверенность алгоритма в принятом значении.

[00034] Согласно варианту заявляемого технического решения (Фиг. 3): предварительно получают информационные биты 101 (Фиг. 3), затем формируют, по крайней мере, два сообщения, где каждое содержит закодированные помехоустойчивым ZigZag кодом вышеуказанные информационные биты, к которым добавлена группа проверочных бит 102 (Фиг. 3) следующим образом.

[00035] Информационные биты на передатчике кодируются помехоустойчивым составным ZigZag кодом, после чего проверочные биты равномерно распределяются по группам - для случая двух сообщений для первого сообщения выбираются четные проверочные биты каждого из четырех компонентных кодов, а для второго - нечетные. При этом в каждом сообщении передаются все информационные биты и одна из частей проверочных бит, т.е. одна группа, причем на разных частотах 103 (Фиг. 3). Методы кодирования низкоплотностных кодов и ZigZag кодов, в частности, широко известны из литературы, например, данные коды описаны в статье [2]. В общем случае, для систематических кодов, к которым относится ZigZag кодирование, - это добавление к исходным информационным битам, которые остаются без изменений, дополнительного количества проверочных бит с помощью особого алгоритма, который позволит в дальнейшем исправить ошибочно принятые информационные биты с использованием проверочных бит. Специалисту в данном уровне техники очевидно, что количество групп может быть более двух, например три группы или более. В этом случае будут передаваться три и более сообщений, в каждом из которых будут все информационные биты и группа проверочных. Правила по разбиению на группы принципиально важны для качественной работы способа. Используемое разбиение на четные и нечетные является одновременно и простым, и оптимальным для выбранного помехоустойчивого ZigZag кода и для двух сообщений. При использовании трех сообщений будет применяться аналогичное разбиение - в первом сообщении будут передаваться биты 1, 4, 7…, во втором 2,5,8,…, в третьем 3,6.9… и так далее, не ограничиваясь.

[00036] Тогда каждое из передаваемых сообщений будет представлять собой кодовое слово составного ZigZag кода с перфорированием. В источнике информации [1] показано, что указанный способ перфорирования обеспечивает качество декодирования полученных с его помощью кодов, которое хорошо соответствует качеству декодирования других помехоустойчивых кодов с аналогичной скоростью. При приеме сообщения на приемнике 104 (Фиг. 3) обнаруженные сообщения декодируются по отдельности 105 (Фиг. 3), при этом начальные метрики для проверочных бит, которые не передавались в декодируемом сообщении, в начале декодирования принимаются равными нулю.

[00037] В случае, если отдельное сообщение не удалось декодировать и если были обнаружены сообщения, которые также не удалось декодировать по отдельности, осуществляется их совместное декодирование, для чего из метрик для всех бит исходных сообщений составляются новые метрики для декодирования проверочного кода. Для этого метрики, соответствующие всем битам в исходных сообщениях, складываются. Тогда метрики для проверочных бит будут нулевыми во всех сообщениях, кроме одного, а метрики для бит данных сложатся, что будет соответствовать общепринятым методам приема кода с повторением. Это самый простой способ получить метрики совместно из нескольких принятых сообщений. Фактически, это просто сложение метрик для всех принятых сообщений. В литературе известен метод maximal-ratio combining, простое сложение - это самый простой его вариант.

[00038] Как уже было сказано, за счет того что данный метод кодирования предполагает передачу всех полезных данных, т.е. информационных бит, в каждом сообщении, возможен успешный прием даже в случае, если все сообщения, кроме одного,… потеряны из-за коллизий или помех в их полосе.

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

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

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

[00042] Согласно примеру осуществления технического решения, при кодировании 240 информационных бит помехоустойчивым кодом скорости 1/3 получаются 480 проверочных бит. Проверочные биты делятся на группы, по четным и нечетным битам, причем четные передаются в первом сообщении, нечетные во втором.

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

[00044] То есть промежуточный результат - получение такого кода скорости 1/2 (из существующего кода 1/3), который по эффективности исправления ошибок не проигрывает другим кодам скорости 1/2, полученным отдельно и независимо. При этом, при получении нескольких сообщений, можно декодировать исходный код 1/3, который позволяет исправить еще больше ошибок. Сам по себе этот процесс передачи только части проверочных бит (называемый перфорированием) известен из литературы.

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

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

[00047] Настоящее подробное описание составлено с приведением различных, не имеющих ограничительного и исчерпывающего характера вариантов осуществления. В то же время специалистам, имеющим средний уровень компетентности в рассматриваемой области техники, очевидно, что различные замены, модификации или сочетания любых раскрытых здесь вариантов осуществления (в том числе частично) могут быть воспроизведены в пределах объема настоящего технического решения. Таким образом, подразумевается и понимается, что настоящее описание включает дополнительные варианты осуществления, суть которых не изложена здесь в явно выраженной форме. Такие варианты осуществления могут быть получены путем, например, сочетания, модификации или преобразования каких-либо действий, компонентов, элементов, свойств, аспектов, характеристик, ограничений и пр., относящихся к приведенным здесь и не имеющим ограничительного характера вариантам осуществления.

ПРИМЕРЫ РЕАЛИЗАЦИИ

[00048] Рассмотрим пример реализации технического решения, в котором необходимо передать 240 бит данных (информационных бит). Для кодирования используется помехоустойчивый ZigZag код с кодовой скоростью 1/3. После завершения процесса кодирования для передачи будут готовы исходные 240 бит данных (информационные биты) и 480 (в два раза больше количества информационных) проверочных бит, всего 720 бит. Проверочные биты делятся на две равные группы по 240 бит, после этого первое сообщение составляется из 240 информационных бит данных и первых 240 проверочных бит, всего 480 бит. Аналогично, второе сообщение состоит из тех же 240 бит данных и оставшихся 240 проверочных бит. Проверочные биты разделяются на две группы и передаются в отдельных сообщениях следующим образом - 1,3,5,7,…, 479 передаются в первом сообщении, а 2,4,6,8,…, 480 передаются во втором сообщении. Информационные биты передаются в каждом сообщении целиком без модификации (Фиг. 2).

[00049] Каждое из передаваемых сообщений представляет собой кодовое слово с перфорированием кодовой скорости 1/2, причем два сообщения, декодируемые совместно, представляют собой исходное кодовое слово скорости 1/3.

[00050] Сформированные таким образом сообщения передаются последовательно на разных частотах. После детектирования первого сообщения производится проверка правильности приема информационных бит. При хороших условиях передачи, когда шумы в канале достаточно малы и не приводят к ошибкам на приеме, информационные биты принимаются сразу верно. Если же первое сообщение принято с ошибками, запускается процедура исправления ошибок с использованием передаваемых в первом сообщении проверочных бит. Для декодирования восстанавливается кодовое слово помехоустойчивого ZigZag кода, при этом метрики информационных бит и проверочных бит 1,3,…, 479 рассчитываются на основе принятых данных, а метрики проверочных бит 2,4,…, 480 принимаются равными нулю.

[00051] Таким образом, из кодового слова с перфорированием кодовой скорости 1/2 восстанавливается кодовое слово исходного кода скорости 1/3 с заменой части метрик нулями. Полученное кодовое слово декодируется.

[00052] Аналогично, после принятия второго сообщения проверяется правильность переданных в нем информационных бит, при необходимости запускается процедура исправления ошибок с использованием передаваемых во втором сообщении проверочных бит. Если же было принято еще и первое сообщение с такими же данными, для восстановления используются все 480 проверочных бит. Для этого восстанавливается кодовое слово, причем метрики проверочных бит 2,4,…, 480 вычисляются по принятым данным, а метрики бит 1,3,…, 479 заменяются нулями, либо, если было принято и не было декодировано первое сообщение, метриками этих бит, вычисленных по данным первого сообщения.

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

[00054] Результаты моделирования помехоустойчивого ZigZag кода в условиях канала с нормальным гауссовским шумом для скоростей 1/3 и 1/2 приведены на Фиг. 1. Видно, что использование кода скорости 1/3 дает выигрыш в требуемом отношении Еb/N0 около 0.5 дБ относительно скорости 1/2. Это значит, что при использовании кодирования со скоростью 1/3 такой же уровень ошибок на приеме достигается при более низком отношении Eb/N0. То есть для передачи данных с таким кодированием требуется потратить меньше энергии на переданный информационный бит. То есть, несмотря на то что при кодировании скоростью 1/3 требуется передавать больше бит, чем при 1/2, например 480 при 1/2 и 720 при 1/3, мощность передатчика при работе с 1/3 может быть значительно ниже.

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

[00056] во-первых, декодирование ZigZag кода производится алгоритмом с линейной сложностью относительно длины кода и содержит главным образом только операции сложения/вычитания и сравнения. Под этим подразумевается то, что для декодирования низкоплотностных кодов не требуется выполнять операции умножения, деления, вычислять тригонометрические и другие специальные функции. Благодаря этому низкоплотностные коды широко используются, в том числе, их возможно использовать в предложенном техническом решении. Во многом именно поэтому выбран ZigZag код, и вся предложенная схема кодирования разрабатывалась с учетом того, что она должна быть практически осуществима;

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

ИСТОЧНИКИ ИНФОРМАЦИИ

1. Construction and analysis of rate-compatible punctured concatenated zigzag codes, Information Theory, 2005. ISIT 2005. Proceedings. International Symposium on, IEEE.

2. Ping L., Huang X., Phamdo N. Zigzag codes and concatenated zigzag codes // Information Theory, IEEE Transactions on. - 2001. - T. 47. - №. 2. - C. 800-807.

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

1. Способ кодирования и декодирования сообщений, в котором:

получают информационные биты;

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

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

принимают, по крайней мере, одно вышеуказанное закодированное сообщение;

декодируют, по крайней мере, одно закодированное сообщение, причем

каждое сообщение декодируют по отдельности;

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

2. Способ по п. 1, характеризующийся тем, что помехоустойчивым кодом является ZigZag код с кодовой скоростью 1/3.

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

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

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

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

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

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

9. Способ по п. 8, характеризующийся тем, что метрики, соответствующие всем битам в исходных сообщениях, складываются.

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

11. Способ по п. 1, характеризующийся тем, что передача сообщений на различных частотах происходит с перерывом по времени.