Способы и устройство, использующие коды с fec с постоянной инактивацией символов для процессов кодирования и декодирования

Способы и устройство, использующие коды с fec с постоянной инактивацией символов для процессов кодирования и декодирования

Иллюстрации

Показать все

Реферат

ПЕРЕКРЕСТНЫЕ ССЫЛКИ

Данная заявка частично продолжает патентную заявку США №12/604773, поданную 23 октября 2009 года (заявители M.Amin Shokrollahi и др.) под заголовком "Method and Apparatus Employing FEC Codes with Permanent Inactivation of Symbols for Encoding and Decoding Processes" и кроме того испрашивает приоритет следующих предварительных заявок (заявители M. Amin Shokrollahi и др.) под названием "Method and Apparatus Employing FEC Codes with Permanent Inactivation of Symbols for Encoding and Decoding Processes": предварительной патентной заявки США №61/353910, поданной 11 июня 2010 года; предварительной патентной заявки США №61/257146, поданной 2 ноября 20009 года; и предварительной патентной заявки США №61/235285, поданной 19 августа 2009 года. Каждая из вышеупомянутых предварительных и не предварительных заявок включена сюда по ссылке для всех целей.

Следующие ссылочные материалы целиком включены сюда посредством ссылки для всех целей:

1) Патент США №6307487, выданный Michael G. Luby под заголовком "Information Additive Code Generator and Decoder for Communication Systems" (далее "Luby I");

2) Патент США №6320520, выданный Michael G. Luby под заголовком "Information Additive Group Code Generator and Decoder for Communication Systems" (далее "Luby II");

3) Патент США №7068729, выданный M. Amin Shokrollahi под заголовком "Multi-Stage Code Generator and Decoder for Communication Systems" (далее "Shokrollahi I");

4) Патент США №6856263, выданный M. Amin Shokrollahi под заголовком "Systems and Processes for Decoding a Chain Reaction Code Through Inactivation" (далее "Shokrollahi II");

5) Патент США №6909383, выданный M. Amin Shokrollahi под заголовком "Systematic Encoding and Decoding of Chain Reaction Codes" (далее "Shokrollahi III");

6) Патентная публикация США №2006/0280254 заявителей Michael G. Luby и M. Amin Shokrollahi под заголовком "In-Place Transformations with Applications to Encoding and Decoding Various Classes of Codes" (далее "Luby III");

7) Патентная публикация США №2007/0195894 заявителей M. Amin Shokrollahi под заголовком "Multiple-Field Based Code Generator and Decoder for Communications Systems" (далее "Shokrollahi IV").

ОБЛАСТЬ ТЕХНИКИ, К КОТОРОЙ ОТНОСИТСЯ ИЗОБРЕТЕНИЕ

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

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

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

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

Также используемый здесь термин «входные данные» относится к данным, присутствующим на входе устройства-кодера с прямым исправлением ошибок (FEC) или модуля, компоненты, шага и т.д. кодера FEC («кодер FEC»), а термин «выходные данные» относится к данным, присутствующим на выходе кодера FEC. Соответственно предполагается присутствие выходных данных на входе декодера FEC, и предполагается, что декодер FEC выдает входные данные или их эквивалент на основе выходных данных, которые он обработал. В некоторых случаях входные данные представляют собой или включают в себя исходные данные, а в некоторых случаях выходные данные представляют собой или включают в себя кодированные данные. В других случаях устройство отправителя (или программный код отправителя) может содержать больше одного кодера FEC, то есть, исходные данные преобразуются в кодированные данные в цепочке, состоящей из множества кодеров FEC. Аналогичным образом, в приемнике может быть более одного декодера FEC, используемого для создания исходных данных из принятых кодированных данных.

Данные можно представить как состоящие из множества символов. Кодер представляет собой компьютерную систему, устройство, электронную схему или т.п., которая создает кодированные символы или выходные символы из последовательности исходных символов или входных символов, а декодер представляет собой дополняющую часть, которая восстанавливает последовательность исходных символов или входных символов из принятых или восстановленных кодированных символов или выходных символов. Кодер и декодер разделены во времени и/или пространстве каналом, причем любые принятые кодированные символы не могут точно совпадать с соответствующими переданными кодированными символами, и не могут приниматься точно в той последовательности, в которой они были переданы. «Размер» символа может измеряться в битах, независимо от того, оказался ли в действительности данный символ в битовом потоке, где символ имеет размер M бит, когда символ выбирается из алфавита, содержащего 2^М символов. Здесь во многих примерах символы измеряются в байтах, и коды могут быть в области, состоящей из 256 возможных вариантов (здесь это 256 возможных 8-битовых шаблонов), но следует понимать, что можно использовать и другие, единицы измерения данных, широко известно много способов измерения данных.

В Luby I описано использование кодов, таких как коды с цепной реакцией, обеспечивающих эффективное исправление ошибок с точки зрения использования вычислительной мощности, памяти и полосы пропускания. Одно из свойств кодированных символов, создаваемых кодером с цепной реакцией, состоит в том, что приемник способен восстановить первоначальный файл, как только принято достаточное количество кодированных символов. В частности, для восстановления К первоначальных символов с высокой вероятностью приемнику необходимо иметь приблизительно К+А кодированных символов.

«Абсолютная величина служебных данных» для данной ситуации представлена значением А, в то время как «относительную величину служебных данных» можно вычислить как отношение А/К. Абсолютная величина служебных данных при приеме является показателем того, сколько дополнительных данных необходимо принять сверх теоретически минимального количества данных, причем этот показатель может зависеть от надежности декодера и может изменяться в функции числа К исходных символов. Аналогичным образом, относительная величина служебных данных при приеме (А/К) является показателем того, сколько дополнительных данных необходимо принять сверх теоретически минимального количества данных по отношению к объему восстанавливаемых исходных данных, причем этот показатель также может зависеть от надежности декодера и может изменяться в функции числа К исходных символов.

Коды с цепной реакцией весьма полезны для осуществления связи по сети с пакетной коммуникацией. Однако иногда они могут быть достаточно интенсивными в плане вычислений. Декодер может декодировать чаще или легче, если исходные символы закодированы с использованием статического кодера до использования динамического кодера, который осуществляет кодирование с использованием кода с цепной реакцией или другого кода без фиксированной скорости. Указанные декодеры описаны, например, в Shokrollahi I. В показанных здесь примерах исходные символы являются входными символами для статического кодера, создающего выходные символы, которые, в свою очередь, являются входными символами для динамического кодера, создающего выходные символы, являющиеся кодированными символами, где динамический кодер является кодером без фиксированной скорости, способный создавать выходные символы в количестве, которое не является фиксированной нормой по отношению к количеству входных символов. Статический кодер может включать в себя более одного кодера с фиксированной скоростью. Например, статический кодер можете включать в себя кодер Хэмминга, кодер с контролем по четности с низкой плотностью («LDPC»), кодер с контролем по четности с высокой плотностью («HDPC») или т.п.

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

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

В Shokrollahi II описан подход, называемый «инактивация» (inactivation), согласно которому декодирование выполняется в два шага. На первом шаге декодер подытоживает, какие имеются принятые кодированные символы, возможный вид матрицы и определяет, по меньшей мере, приблизительно последовательность шагов декодирования, которые позволят завершить обработку цепной реакции с данными принятыми кодированными символами. На втором шаге декодер выполняет декодирование на основе цепной реакции в соответствии с определенной последовательностью шагов декодирования. Это может быть реализовано эффективным образом с точки зрения использования памяти (то есть, таким образом, который потребует меньший объем памяти для операции, чем менее эффективный с точки зрения использования памяти процесс).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

фиг. 2 - таблица переменных, массивов и т.п., используемых здесь в различных других чертежах;

фиг. 3 - блок-схема конкретного варианта осуществления кодера, показанного на фиг. 1;

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

фиг. 5 - блок-схема, иллюстрирующая процесс кодирования с постоянной инактивацией (PI);

фиг. 6 - блок-схема, иллюстрирующая процесс динамического кодирования;

фиг. 7 - блок-схема операции вычисления веса для вычисления символов;

фиг. 8 - таблица, которая может храниться в памяти и использоваться для определения степени символа на основе искомого значения;

фиг. 9 - матрица, используемая в процессе кодирования или декодирования;

фиг. 10 - уравнение, представляющее части матрицы, показанной на фиг. 9, для конкретного минимального полинома;

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

фиг. 12 - матричное представление набора уравнений, решаемых декодером для восстановления массива С(), представляющее восстановленные исходные символы из массива D(), представляющее принятые кодированные символы с использованием субматрицы SE, представляющей R статических символов или уравнений, известных декодеру;

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

фиг. 14 - блок-схема, описывающая процесс создания матрицы по фиг. 12;

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

фиг. 16 - блок-схема, иллюстрирующая процесс создания субматрицы LT, которую можно использовать в матрице по фиг. 12 или матрице по фиг. 15;

фиг. 17 - блок-схема, иллюстрирующая процесс создания субматрицы PI, которую можно использовать в матрице по фиг. 15;

фиг. 18 - блок-схема генератора матрицы;

фиг. 19 - блок-схема, иллюстрирующая процесс создания субматрицы SE;

фиг. 20 - блок-схема, иллюстрирующая процесс создания субматрицы PI;

фиг. 21 - блок-схема, иллюстрирующая процесс нахождения восстановленных символов в декодере;

фиг. 22 показывает матричное представление после перестановок набора уравнений, решаемых декодером для восстановления массива C(), представляющее восстановленные исходные символы из массива D(), который представляет принятые кодированные символы;

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

фиг. 24 показывает матричное представление, используемое как часть процесса декодирования;

фиг. 25 показывает матричное представление, используемое как другая часть процесса декодирования;

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

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

фиг. 28 показывает матричное представление набора уравнений, решаемых декодером;

фиг. 29 показывает матричное представление набора уравнений, решаемых декодером;

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

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

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

ПОДРОБНОЕ ОПИСАНИЕ КОНКРЕТНЫХ ВАРИАНТОВ ОСУЩЕСТВЛЕНИЯ ИЗОБРЕТЕНИЯ

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

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

Некоторые из раскрытых здесь вариантов осуществления могут быть применены ко многим другим типам кодов, например, к кодам, описанным в Internet Engineering Task Force (IETF) (специальная комиссия интернет разработок) Request for Comments (RFC) (запрос на комментарии) 5170 (далее «коды IETF LDPC») и к кодам, описанным в патентах США №№6073250, 6081909 и 6163870 (далее «коды Торнадо»), что приводит к повышению надежности и/или улучшению рабочих характеристик компьютера и/или памяти для указанных типов кодов.

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

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

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

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

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

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

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