Динамическое перемежение потоков и доставка на основе подпотоков

Динамическое перемежение потоков и доставка на основе подпотоков

Иллюстрации

Показать все

Реферат

Перекрестная ссылка на родственные заявки

Данная заявка испрашивает приоритет предварительной заявки на патент США номер 60/912145, озаглавленной "Dynamic Stream Interleaving and Sub-Stream Based Delivery", поданной 16 апреля 2007 года. Содержимое этой заявки полностью включено в данном документе посредством ссылки для всех целей.

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

Патент США №6307487 на имя Luby (в дальнейшем "Luby I");

Патент США №7068729 на имя Shokrollahi и др. (в дальнейшем "Shokrollahi I");

Патентная заявка США №11/423391, поданная 9 июня 2006 и озаглавленная "Forward Error-Correcting (FEC) Coding and Streaming", на имя Luby и др. (в дальнейшем "Luby II"); и

Патентная заявка США №11/674625, поданная 13 февраля 2007 года, озаглавленная "Streaming and Buffering Using Variable FEC Overhead and Protection Periods", на имя Watson и др. (в дальнейшем "Watson").

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

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

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

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

В последнее время стало установившейся практикой рассматривать использование кодов прямой коррекции ошибок (FEC) для защиты потокового мультимедиа во время передачи. Когда отправляется по пакетной сети, примеры которой включают в себя Интернет и беспроводные сети, такие как стандартизированные посредством таких групп, как 3GPP, 3GPP2 и DVB, исходный поток помещается в пакеты по мере того, как он формируется или становится доступным, и тем самым пакеты используются для того, чтобы переносить исходный поток или поток содержимого в том порядке, в котором он формируется или становится доступным, в приемники.

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

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

Имеется много примеров FEC-кодов, которые могут использоваться для того, чтобы предоставлять защиту исходного потока. Коды Рида-Соломона - это известные коды для коррекции ошибок и стирания в системах связи. Для коррекции стирания, например, в сетях пакетной передачи данных известная эффективная реализация кодов Рида-Соломона использует матрицы Коши или Вандермонда, как описано в L. Rizzo, "Effective Erasure Codes for Reliable Computer Communication Protocols", Computer Communication Review, 27 (2): 24-36 (апрель 1997 года) (в дальнейшем "Rizzo") и Bloemer и др., "An XOR-Based Erasure-Resilient Coding Scheme", Technical Report TR-95-48, International Computer Science Institute, Berkeley, California (1995) (в дальнейшем "XOR-Reed-Solomon"), или в других источниках.

Другие примеры FEC-кодов включают в себя LDPC-коды, коды цепной реакции, такие как описанные в Luby I, и коды многостадийной цепной реакции, такие как в Shokrollahi I.

Примеры процесса FEC-декодирования для разновидностей кодов Рида-Соломона описываются в Rizzo и XOR-Reed-Solomon. В этих примерах декодирование применяется после того, как принято достаточно исходных и исправляющих пакетов данных. Процесс декодирования может требовать большого объема вычислений, и, в зависимости от доступных ресурсов CPU, его выполнение может отнимать большое количество времени относительно длительности времени, охватываемой посредством мультимедиа в блоке. Приемник должен принимать во внимание эту длительность времени, требуемую для декодирования, при вычислении задержки, требуемой между началом приема медиапотока и воспроизведением медиа. Эта задержка, обусловленная декодированием, воспринимается пользователем как задержка между его запросом на предмет конкретного медиапотока и началом воспроизведения. Таким образом, желательно минимизировать эту задержку.

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

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

Для некоторых FEC-кодов, а именно кодов Рида-Соломона, время кодирования и декодирования становится непрактичным по мере того, как число кодированных символов на исходный блок возрастает. Таким образом, на практике зачастую предусмотрена целесообразная верхняя граница (255 - это приблизительное целесообразное ограничение для некоторых приложений) для общего числа кодированных символов, которые могут быть сформированы на исходный блок, в частности, в типичном случае, где процесс кодирования и декодирования по Риду-Соломону выполняется посредством специализированных аппаратных средств, к примеру, MPE-FEC-процессы, которые используют коды Рида-Соломона, включенные как часть DVB-H-стандарта, для защиты потоков от потери пакетов, реализуются в специализированных аппаратных средствах в сотовом телефоне, который ограничен всего 255 кодированными символами Рида-Соломона на исходный блок. Поскольку символы зачастую должны помещаться в отдельные рабочие данные пакета, это задает целесообразную верхнюю границу на максимальную длину кодированного исходного блока. Например, если рабочие данные пакета ограничены 1024 байтами или менее и каждый пакет переносит один кодированный символ, то кодированный исходный блок может составлять самое большее 255 Кбайт (килобайт), и это, разумеется, также является верхней границей размера самого исходного блока.

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

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

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

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

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

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

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

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

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

Таким образом, желательно совершенствовать процессы и устройство.

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

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

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

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

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

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

Фиг.1 - блок-схема системы связи согласно одному варианту осуществления настоящего изобретения.

Фиг.2 - схема, иллюстрирующая время на переключение содержимого.

Фиг.3A - чертеж, иллюстрирующий компоненты времени на переключение содержимого.

Фиг.3B - чертеж, иллюстрирующий использование CPU для FEC во время декодирования.

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

Фиг.5 - чертеж, иллюстрирующий структуру кодированных блоков, соответствующих потоку содержимого по фиг.4.

Фиг.6 - чертеж, иллюстрирующий приемник и время на переключение содержимого, соответствующее базовому способу отправки.

Фиг.7 - чертеж, иллюстрирующий ленточный способ отправки потока.

Фиг.8 - чертеж, иллюстрирующий статическое перемежение согласно ленточному способу отправки потока.

Фиг.9 - чертеж, иллюстрирующий приемник и время на переключение содержимого, соответствующее способу отправки со статическим перемежением.

Фиг.10 - чертеж, иллюстрирующий способ отправки с динамическим перемежением, когда новый поток отправляется в приемник.

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

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

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

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

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

Подробное описание

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

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

Символы могут переноситься по сети передачи данных в пакетах, при этом целое число символов явно переносится или подразумевается в каждом пакете. В некоторых случаях возможно, что исходный пакет не является кратным длине символа, в этом случае последний символ в пакете может усекаться. В этом случае, в целях FEC-кодирования неявно предполагается, что этот последний символ дополняется до конца фиксированной комбинацией битов, к примеру битов с нулевым значением, так что даже если эти биты не переносятся в пакете, приемник по-прежнему может заполнять этот последний усеченный символ до полного символа. В других вариантах осуществления фиксированная комбинация битов может быть помещена в пакет, тем самым фактически дополняя символы до длины, равной длине пакета. Размер символа зачастую может измеряться в битах, при этом символ имеет размер M битов и символ выбирается из алфавита в 2^M (два в степени M) символов. Недвоичные цифры также рассматриваются, но биты предпочтительны, поскольку они чаще всего используются.

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

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

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

Пример FEC-кода

Фиг.1 - это блок-схема системы 100 связи, которая использует FEC-кодирование с цепной реакцией. В системе 100 связи входной файл 101 или входной поток 105 предоставляется в формирователь 110 входных символов. Формирователь 110 входных символов формирует последовательность из одного или более входных символов (IS(0), IS(1), IS(2), …) из входного файла или потока, при этом каждый входной символ имеет значение и позицию (обозначаемые на фиг.1 как целое число в скобках). Возможные значения для входных символов, т.е. их алфавит, - это типично алфавит из двух миллионов символов, так что каждый входной символ кодирует M битов входного файла. Значение M, в общем, определяется при помощи системы 100 связи, но система общего назначения может включать в себя ввод размера символа для формирователя 110 входных символов так, чтобы M могло варьироваться каждый раз. Вывод формирователя 110 входных символов предоставляется в кодер 115.

Формирователь 120 ключей формирует ключ для каждого выходного символа, который должен формироваться посредством кодера 115. Каждый ключ может быть сформирован согласно одному из способов, описанных в Luby I или в Shokrollahi I, или любому сравнимому способу, который обеспечивает то, что значительная часть ключей, формируемых для одного входного файла или блока данных в потоке, является уникальной, независимо от того, формируются ли они посредством этого или другого формирователя ключей. Например, формирователь 120 ключей может использовать комбинацию вывода счетчика 125, уникального идентификатора 130 потока и/или вывода случайного формирователя 135, чтобы формировать каждый ключ. Вывод формирователя 120 ключей предоставляется в кодер 115. В других примерах, например в некоторых приложениях потоковой передачи, набор ключей может быть фиксированным и повторно использованным для каждого блока данных в потоке. В типичном варианте осуществления число ключей, которые могут быть сформированы, диктуется посредством разрешения формирователя ключей, а не размера или другой характеристики входного файла или потока. Например, если, как ожидается, ввод составляет зачастую порядка тысячи символов или менее, ключевое разрешение может составлять 32 бита, обеспечивая до 4 миллиардов уникальных ключей. Один результат этих относительных чисел состоит в том, что кодер, который кодирует согласно ключам, может допускать формирование 4 миллиардов уникальных выходных символов для четырех тысяч символов ввода. На практике большинство систем связи не должны терять 0,999999 части символов, так что нигде не потребуется формировать порядка 4 миллиардов выходных символов, и поэтому число возможных ключей может трактоваться как фактически неограниченное и не обязательно должно повторяться, и вероятность, что два независимых выбора ключей захватят одинаковый ключ, является незначительно малой. Тем не менее, если это произошло по какой-либо причине, разрешение формирователя ключей может быть увеличено так, что процессы, которые используют ключи, могут действовать, как если бы ключи предоставлялись бесконечно.

Из каждого ключа I, предоставляемого посредством формирователя 120 ключей, кодер 115 формирует выходной символ со значением B(I) из входных символов, предоставляемых посредством формирователя входных символов.

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

Кодер 115 предоставляет выходные символы в передающий модуль 140, и формирователь 120 ключей предоставляет ключ каждого такого выходного символа в передающий модуль 140. Передающий модуль 140 передает выходные символы, и, в зависимости от используемого способа манипуляции, передающий модуль 140 также может передавать некоторые данные о ключах передаваемых выходных символов по каналу 145 в приемный модуль 150. Предполагается, что канал 145 является каналом со стиранием, но это необязательно для надлежащей работы системы 100 связи. Модули 140, 145 и 150 могут быть любыми подходящими аппаратными компонентами, программными компонентами, физическими средами или любой комбинацией вышеозначенного, до тех пор пока передающий модуль 140 выполнен с возможностью передавать выходные символы и все необходимые данные о своих ключах в канал 145, а приемный модуль 150 выполнен с возможностью принимать символы и потенциально некоторые данные о своих ключах от канала 145. Значение K, если используется для того, чтобы определять ассоциирование, может отправляться по каналу 145 или оно может задаваться заранее в соответствии с согласованием кодера 115 и декодера 155.

Канал 145 может быть каналом реального времени, таким как тракт через Интернет или широковещательная линия связи от телевизионного передающего устройства в телевизионный приемник, или телефонное соединение от одной точки к другой, либо канал 145 может быть каналом с памятью, таким как CD-ROM, накопитель, веб-узел и т.п. Канал 145 даже может быть комбинацией канала реального времени и канала с памятью, такой как канал, формируемый, когда один пользователь передает входной файл из персонального компьютера поставщику Интернет-услуг (ISP) по телефонной линии связи, входной файл сохраняется на веб-сервере и впоследствии передается получателю по Интернету.

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

Приемный модуль 150 предоставляет выходные символы в декодер 155, и все данные, которые приемный модуль 150 принимает о ключах этих выходных символов, предоставляются в повторный формирователь 160 ключей. Повторный формирователь 160 ключей восстанавливает ключи для принимаемых выходных символов и предоставляет эти ключи в декодер 155. Декодер 155 использует ключи, предоставляемые посредством повторного формирователя 160 ключей, вместе с соответствующими выходными символами для того, чтобы восстанавливать входные символы (снова IS(0), IS(1), IS(2), …). Декодер 155 предоставляет восстановленные входные символы в повторный сборщик 165 входных файлов, который формирует копию 170 входного файла 101 или копию 175 входного потока 105.

Приложения потоковой передачи мультимедиа

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

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