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

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

 

Изобретение относится к области передачи данных с использованием решающей обратной связи в протоколах вычислительных и информационных систем. Способы передачи с решающей обратной реализуют переспрос сообщения, закодированного помехоустойчивым кодом, если на приемной стороне обнаружены ошибки. Принципы построения таких систем (системы с автоматическим запросом на повторение - АЗП, ARQ) изложены, например, в монографии S.Lin and D.J.Costello, Jr. Error Control Coding: Fundamentals and Applications. NJ:Englewood Cliffs. 2001. Современное состояние вопроса изложено в обзорной статье A. Ahmed, A. Al-Dweik, Y. Iraqi, Н. Mukhtar, М. Naeem and Е. Hossain, "Hybrid Automatic Repeat Request (HARQ) in Wireless Communications Systems and Standards: A Contemporary Survey, IEEE Communications Surveys & Tutorials, vol. 23, no. 4, pp. 2711-2752, Fourthquarter 2021, doi: 10.1109/COMST.2021.3094401.

В традиционных способах автоматического запроса на повторение (ARQ) ошибки в передаваемых пакетах проверяются на принимающей стороне с помощью кода с обнаружением ошибок (обычно контроль циклическим избыточным кодом (CRC) или иным подходящим избыточным кодом). Если при контроле на приемной стороне в кадре не обнаружено ошибок, принимающая сторона отправляет получателю уведомление об успешном получении (АСК). Если в кадре обнаружена ошибка, принимающая сторона отправляет сигнал отрицательного уведомления о получении (NAK), запрашивая повторную передачу.

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

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

В реальных каналах с изменяющимися условиями передачи (изменении отношения сигнал-шум (SNR)), таких как мобильные и спутниковые каналы, применяют способы HARQ - Туре 2 с накоплением и обработкой принятых повторно комбинаций (HARQ-CC) или с передачей при переспросе дополнительных избыточных символов (с инкрементной избыточностью, HARQ-IR). Такие способы демонстрируют более высокую пропускную способность за счет адаптации избыточности кода с исправлением ошибок к разным условиям канала.

Характеристика уровня техники

Известен аналог предлагаемого изобретения, относящийся к способам с накоплением принятых комбинаций (HARQ-CC) СПОСОБ ПЕРЕДАЧИ-ПРИЕМА СООБЩЕНИЙ В СИСТЕМАХ СВЯЗИ. Патент РФ на ИЗ №2595627, 2015 г. (Аналог 1). Технический результат изобретения заключается в повышении скорости приема информации за счет снижения вероятности переспросов.

Способ передачи-приема сообщений в системах связи, заключается в том, что на передающей стороне исходное сообщение разбивают на порции по к бит, формируют из них кадры со структурой протокола HDLC методом ARQ на h шагов назад, передают h кадров по каналу связи, где h>3, на приемной стороне по контрольной последовательности протокола HDLC обнаруживают ошибочные кадры, если ошибочные кадры отсутствуют, информационные k бит выдают получателю или стирают кадр с ошибками, блокируют прием последующих h-1 кадров, по обратному каналу посылают команду запроса и передающая сторона повторно передает эти h кадров, отличающийся тем, что h кадров предварительно располагают в двумерный массив из i строк и j столбцов h=i×j для каждой s-й строки, где s = 1, 2 … i, вычисляют первую совокупность контрольных кадров m_s,j+1, равных сумме кадров строки по модулю два, вычисляют вторую совокупность контрольных кадров m_i+1,t равных сумме кадров столбца по модулю два, где t = 1, 2 … J, сформированный массив из i+1 строк и j+1 столбцов передают в канал связи, после приема в принятом массиве обнаруживают по контрольной последовательности протокола HDLC кадры с ошибками, стирают их, определяют число стертых кадров в каждой из i+1 строк, если стерт один кадр m_s,t восстанавливают его путем замены на по модулю 2, где l≠t, определяют число стертых кадров в каждом из (j+1) столбцов, при стирании одного кадра m_s,t восстанавливают его путем замены: на по модулю 2, где l≠t, определяют число стертых кадров в каждом из (j+1) столбцов, при стирании одного кадра m_s,t восстанавливают его путем замены на по модулю 2 где v≠s, если в полученном двумерном массиве i×j нет стертых кадров, к информационных бит каждого из h кадров выдают получателю, иначе повторно восстанавливают стертые кадры в каждых из i+1 строк и j+1 столбцов, если и после повторного просмотра остались стертые кадры, по каналу обратной связи производят переспрос этих h кадров.

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

Недостатком рассматриваемого изобретения является, полное дублирование передаваемого по запросу блока, ограниченная корректирующая способность итеративного кодирования, что снижает скорость передачи. Способ имеет по сообщению автором ограниченную область применения: использование протокола с блокировкой и возвращением на h шагов (аналогичного HDLC) и пригоден для каналов с большой задержкой распространения сигнала.

Известен аналог, относящийся к способам HARQ IR. Патент РФ на ИЗ №2239952 СПОСОБ ПЕРЕДАЧИ СООБЩЕНИЙ В СИСТЕМАХ С ОБРАТНОЙ СВЯЗЬЮ (аналог 2).

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

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

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

Наиболее близким к предлагаемому способу является способ, описанный в работе М. S. Mohammadi, I. В. Collings and Q. Zhang, "Simple Hybrid ARQ Schemes Based on Systematic Polar Codes for IoT Applications," in IEEE Communications Letters, vol. 21, no. 5, pp. 975-978, May 2017, doi: 10.1109/LCOMM.2017.2662012.

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

Способ передачи использует схему HARQ-IR, основанную на систематических полярных кодах или иных кодовых конструкциях, допускающих разделение избыточных бит на непересекающиеся сегменты. Систематический полярный код произвольной скорости R = К/N, где К - число информационных символов, N-длина кода, позволяет разделить избыточные биты на произвольное число непересекающихся наборов и последовательно передавать систематические биты, а затем избыточные сегменты, пока сообщение не будет успешно декодировано и доставлено получателю.

Предложенный авторами способ использует на начальном шаге кодирование сообщения длиной (К - С) символов которые кодируются кодом обнаружения ошибок С0, С-количество проверочных символов. Выходной вектор длины К обозначается Xs и отправляется по каналу. Обозначим набор переданных систематические бит Т1. Если приемник обнаруживает ошибку в Xs, то на передающей стороне Xs кодируется систематическим полярным кодом С1 со скорости R=K/N и отправляется набор из r1 избыточных символов Р1, где r1 = |Р1| - это общее количество битов в Р1. Затем декодируется полярный код, с помощью процедуры которая включает в себя все К систематических бит кода плюс биты Р1, что образует вектор T₂=T₁+r₁. Восстановленный вектор Xs декодируется с обнаружением ошибки в коде С0 и если ошибки обнаружены, то передатчик отправляет другое непересекающееся подмножество размера r2 избыточных битов Р2. Эта процедура заканчивается, когда контрольная сумма С0 непротиворечива, но потенциально продолжается до тех пор, пока все избыточные биты не будут отправлены на приемную сторону, т.е. когда

Прототип обладает рядом недостатков:

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

• для реализации способа требуется накопитель значительной длины и существенная задержка информации;

• способ может быть использован для ограниченного класса кодов.

Характеристика сведений, раскрывающих сущность изобретения

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

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

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

Такие системы образуются многими типами кодов - БЧХ, Рида-Соломона, Рида-Маллера, полярными и иными. Исчерпывающее описание систем вложенных кодов содержится в книге Э.Л. Блох, В.В. Зяблов Линейные каскадные коды, М.: Наука, 1982, 229 с.

Пусть А₀[n,k₀,d₀]-линейный код длины n с k₀ информационными символами, минимальным расстоянием d₀. Для такого кода будем рассматривать систему вложенных кодов и их смежных классов с параметрами A_i[n,k_i,d_i], i=0,…,m. Для системы выполняются соотношения:

Рассмотрим систему двух вложенных линейных кодов A₀[n,k₀,d₀] и A₁[n,k₁,d₁], таких, что А₀ есть объединение смежных классов A₁. Такая система задается порождающей матрицей где G₀ (k₀ х n) порождающая матрица кода A₀,G₁- (k₁ х n), порождающая матрица A₁, G₀₁- ((k₀-k1) х n) матрица, порождающая образующие смежных классов. Пусть код используется в режиме обнаружения ошибок, а код - в режиме с исправлением ошибок. В начале передачи от источника поступает k0 символов, кодируются с помощью умножения на матрицу, при этом вектор кода является смежным классом кода, номер которого определяется символами. Информационный вектор сохраняется и сохраняется номер смежного класса.

Если ошибок не возникает - информационные символы выдаются получателю и на передающую сторону поступает подтверждение АСК. Процесс передачи продолжается таким образом далее, до момента обнаружения ошибки в некотором кодовом слове.

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

Если в этом принятом векторе не обнаружены ошибки при декодировании с обнаружением в коде декодер по номеру смежного класса определяет образующий смежного класса, переводит сохраненный вектор в смежный класс кода и декодирует с исправлением ошибок в коде А₁. При успешном декодировании получателю выдается k₀+k₁ символов. Заметим, что аналогичная ситуация в обычной системе с переспросом обеспечила бы выдачу только k0 символов. В случае прототипа передача 2n символов в канале также привела бы к выдаче только k0 символов.

Дополнить рассмотрение можно следующим примером. Пусть используется система из двух вложенных кодов БЧХ А₀[31,25,4] и A₁[31,15,8]. Код А0 используется в режиме обнаружения ошибок, а код А1 в режиме исправления трех и менее ошибок. Пусть в трех подряд переданных блоках произошли ошибки кратности Т ≤ 3, а четвертый принят безошибочно. Тогда в соответствии с описанием способа, после приема четвертого вектора и исправления ошибок в трех предыдущих, из накопителя получателю будет выдано 25+15+15+15=70 двоичных символов. В случае обычной ARQ после трех переспросов получателю поступит только 25 символов.

Для рассматриваемого примера можно получить очевидную оценку средней скорости, справедливые для случая приемного накопителя для кодовой комбинации бесконечного объема: , где - вероятность обнаружения ошибок при декодировании в коде А₀. Пример хорошо иллюстрирует возможный выигрыш по скорости, но для его реализации требуется приемный буфер значительной длины, что увеличивает среднюю задержку выдачи сообщения. Кроме того, использование процедуры исправления и обнаружения может увеличивать вероятность необнаруженной ошибки по сравнению со стандартным способом использования CRC16 или CRC32.

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

Используем систему

Соответствующие им порождающие матрицы имеют вид: при этом размерности матриц Выполняются очевидные условия

Система вложенных кодов может быть построена так, что

Дадим описание основной идеи способа.

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

Если же на приемной стороне при выполнении CRC проверки обнаружены ошибки, принятый блок сохраняется и на передающую сторону по каналу ОС поступает сигнал обнаружения ошибки NACK. По этому сигналу кодер на приемной стороне формирует следующий вектор. Структура кодовых слов представлена на фиг.1. При этом первые k₂ символов получают от источника, следующие k₁-k₂ повторяют символы от предыдущего вектора на позициях от k₁+1 до k₀. Эти символы задают номер смежного класса кода А1, которому принадлежит ранее переданный вектор. Символы с номерами k₁+1 до k₀ заполняются нулями, для того чтобы при кодировании вектор у принадлежал коду A₁. Сформированное кодовое слово выдается в канал.

На приемной стороне выполняется обнаружение ошибок в коде А₀. Если принято решение об отсутствии ошибок информационные символы декодируются, номер смежного класса используется для определения образующего смежного класса для перевода в код A₁. Затем производится декодирование с исправлением ошибок с последующей проверкой. Если ошибка не обнаружена, получателю выдаются k₁ информационных символов из накопителя , а затем k2 символов из накопителя

Если после прием блока y возникает ошибка, приемник по запросу передает повторно. При идущих подряд запросах повторение продолжается поочередно.

Таким образом, за счет использования при переспросе кода A₁ с исправлением ошибок, уменьшается количество переспросов, при этом структура вложенных кодов позволяет дополнительно передать при запросе новые символы в кодовых словах длины n и ограничить количество сохраняемых кодовых векторов.

При практической реализации целесообразным является использование в качестве кода А₀ без избыточного кода с параметрами k₀=n и d=1. При этом обнаружение ошибок может осуществляться с помощью циклического кода - (CRC). Это создает возможность применить способ в существующих системы связи без вмешательства в аппаратную часть, за счет реализации на уровне формирования полезной нагрузки пакета. Одновременно выполнение проверок CRC-16 или CRC-32 обеспечивает малую вероятность не обнаруживаемых ошибок.

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

На передающей стороне.

Для реализации способа передающая сторона должна располагать двумя накопителями для хранения кодовых векторов длины и счетчиком поступающих из обратного канала сигналов NACK -N в начале передачи Передатчик ожидает поступления сигнала ОС (фиг.1). Будем полагать, что формирование первого кодового блока происходит по поступлению АСК от приемника. Если ОС=АСК, то и от источника поступает набор информационных символов u_n. Часть символов сохраняют в накопителе производят кодирование Результат кодирования сохраняют в накопителе Производят кодирование циклическим помехоустойчивым кодом, образуя набор CRC Передают в канал для приемника последовательность символов из накопителя с добавленным CRC: После передачи пакета приемник переходит в ожидание сигнала ОС. Если принят сигнал АСК, то последовательность действий, описанная в предыдущем абзаце, повторяется.

Если принят сигнал NACK, то счетчик количества переспросов увеличивается на единицу: N=N+1 и производят проверку значения N. Если N=1 (первый NACK после предшествующего АСК), то формируют новый кодовый вектор При этом от источника получают k₂ символов Этот набор вместе с сохраненным и набором нулевых символов длины n-k₁ используют для кодирования:

. Вектор теперь принадлежит коду А₁. Для него вычисляют и передают в канал на приемную сторону, переходят к ожиданию очередного сигнала ОС. Структура изображена на фиг.2.

Если количество поступивших по каналу ОС последовательных сигналов NACK N≠1, то передают поочередно блоки для четного и нечетного значений N соответственно, до момента получения ACK или исчерпания лимита повторений (на фиг.1 не показано).

На приемной стороне

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

Если в пакете не обнаружены ошибки, CRC(Z)=Ok, по восстанавливают сообщение из n символов , используя преобразование, обратное кодированию. По обратному каналу при этом передают сигнал подтверждения ОС=ACK, N=0, накопителя очищаются, переходят к приему очередного сообщения из канала.

Если в пакете обнаружены ошибки, принятый блок сохраняют в накопителе формируют сигнал OC=NACK, счетчик количества запросов меняет состояние N=N+1, переходят к приему очередного сообщения из канала.

При любом нечетном N (N=1mod2), в накопителе приемника уже содержится ранее принятый пакет с обнаруженным сочетанием ошибок. Принятый пакет сохраняют в накопителе подвергают проверке на CRC и, если ошибок не обнаружено, восстанавливают символы, определяющие номер смежного класса и набор информационных символов используя обратимость операции кодирования. Если проверка CRC пакета привела к обнаружению ошибки, то производят декодирование в коде A₁ с исправлением ошибок и последующей проверке CRC. При удачной попытке исправления ошибок восстанавливают Если попытка декодирование не привела к исправлению ошибок, то в канал ОС отправляют NACK, увеличивают значение счетчика N=N+1 и переходят к ожиданию очередного пакета из канала.

Если же успешно декодирован (или принят без ошибок), то полученные в нем символы задают номер смежного класса и позволяют выполнить декодирование кодового вектора из накопителя в коде A₁ с исправлением ошибок и проверкой CRC.

Если декодирование в коде A₁ успешно, то выделяют k₁ символов, объединяют с n-k₁ символами (напомним, что n-k1=k1-k2) и k₂ символами, полученными из вектора Получателю выдают n+k₂ символов, передают в обратный канал ОС=ACK, счетчик обнуляют N=0, накопители очищают Х=0 Y=0, переходят к ожиданию следующего пакета. Если же декодирование в коде A₁ не успешно, то в канал ОС отправляют NACK, увеличивают значение счетчика N=N+1 и переходят к ожиданию очередного пакета из канала.

При любом четном N≠0 (N=0 mod2) принятый пакет помещают в накопитель производят проверку CRC. Если ошибок не обнаружено, то выделяют номер смежного класса и декодируют коде А₂ с последующей проверкой CRC. Если декодирование в коде А₂ успешно, получателю выдают n+k₂ символов, передают в обратный канал ОС:=ACK, устанавливают N=0, Х=0, Y=0 и переходят к ожиданию следующего пакета.

Если же в вычисление CRC привело к обнаружению ошибки, то в канал ОС отправляют NACK, увеличивают значение счетчика N=N+1 и переходят к ожиданию очередного пакета из канала.

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