СПОСОБ И УСТРОЙСТВО ИЗБИРАТЕЛЬНОГО УПЛОТНЕНИЯ ДАННЫХ
METHOD AND APPARATUS SELECTIVE DATA COMPRESSION

Область техники, к которой относится изобретение
Настоящее изобретение относится в целом к системам дальней связи и способам эффективной передачи данных в этих системах, более точно, к системам и способам определения возможности передачи некоторых сигналов в уплотненной форме.
Предпосылки создания изобретения
За последние десятилетия появились цифровые сети телефонной связи, факсимильной связи, передачи данных и видеосигналов. Учитывая огромный объем данных, обмен которыми осуществляется по сетям связи, очевидно, что уплотнение данных является полезным средством повышения эффективности эксплуатации этих сетей путем передачи сигналов в уплотненной форме, чтобы тем самым использовать доступную полосу пропускания для одновременной передачи большего количества информации. Снижение затрат и экономия времени, а также выгоды более высокоскоростной связи являются весьма значительными и в высшей степени желательными, что создает постоянную потребность в усовершенствовании алгоритмов уплотнения данных без потерь.
Уплотнение данных является методом, в котором сигнал или данные компьютеров, для представления которых требуется определенное число битов, отображаются или кодируются с использованием меньшего числа битов. Соотношение числа битов, необходимого для отображения исходного сигнала, и числа битов, необходимого для отображения кодированного сигнала, известно как коэффициент уплотнения. Дополняющий уплотнение процесс, в ходе которого сигнал или данные компьютеров восстанавливают до исходного представления, называется разуплотнением, декодированием или восстановлением.
Уплотнение данных является одной из технологий, которая сформировалась в последние десятилетия, и включает два основных типа: с потерями и без потерь. В системе уплотнения с потерями часть данных, которые признаны менее необходимыми, отбрасывается, что делает невозможным точное восстановление или разуплотнение сигнала. Уплотнение с потерями применяется в отношении физических сигналов, таких как речевой сигнал, аудиосигнал и видеосигнал, для восприятия которых обычно не требуется точное восстановление исходного сигнала. Поскольку такие сигналы, как описаны выше, обычно предназначены для их восприятия людьми, например, слушателями или зрителями, незначительные различия между исходными и восстановленными сигналами могут не распознаваться органами чувств человека или быть приемлемыми.
В отличие от этого, уплотнение без потерь позволяет точно восстанавливать исходный сигнал после его разуплотнения. Иными словами, уплотнение без потерь обеспечивает совершенное восстановление исходного сигнала без ухудшения или ущерба для характеристик, как при уплотнении с потерями. Одним из недостатков уплотнения без потерь является значительное снижение коэффициента уплотнения или способности уплотнять большое число информационных битов в меньшее число информационных битов. Для данных некоторых типов крайне необходимо осуществление совершенного восстановления уплотненных без потерь данных, а не восстановление с ущербом для характеристик, как в случае уплотнения с потерями. Например, должны точно восстанавливаться данные компьютеров во избежание возможных катастрофических последствий.
В патенте US 6289130 описана схема уплотнения данных согласно алгоритму, позволяющему определять, когда и как следует эффективно переключаться между прозрачным режимом и режимом с уплотнением, чтобы обеспечивать улучшенный коэффициент уплотнения. Кроме того, предложен временной буфер для использования кодером, когда он определяет, какой режим, прозрачный режим или режим с уплотнением, обеспечивает более эффективную передачу части данных. При решении о переходе из одного режима передачи в другой также учитываются издержки, сопутствующие таким переходам.
В патенте US 5177480 описан способ обработки данных для передачи от передатчика приемнику, которые в обоих случаях способны переключаться между режимом с уплотнением, в котором поток данных кодируют с использованием алгоритма уплотнения данных, и прозрачным режимом, в котором поток данных передают в незакодированной форме. В описанном способе считывают в приемнике поток входных данных, кодируют по меньшей мере часть потока входных данных с помощью алгоритма уплотнения данных, чтобы получить поток уплотненных данных, отслеживают эффективность уплотнения потока уплотненных данных и управляют переключением режима передатчика с целью эффективной передачи потока входных данных. В прозрачном режиме приемник и передатчик независимо контролируют эффективность уплотнения и переходят в режим с уплотнением, если установлена неэффективность прозрачного режима. В режиме уплотнения передатчик определяет эффективность уплотнения и передает приемнику управляющий код для перехода как приемника, так и передатчика в прозрачный режим, если установлена неэффективность режима с уплотнением.
В патенте US 5648773 описаны синхронизированные передатчик и приемник в системе уплотнения и передачи данных, которые способны переходить, когда уплотнение перестает быть эффективным, из первого режима работы с уплотнением данных во второй режим работы, называемый свободным режимом, в котором данные передают и принимают непосредственно без уплотнения или разуплотнения при передаче и приеме, соответственно, заданного количества данных.
В патенте US 7263233 описан кодер, способный работать в режиме с уплотнением или в прозрачном режиме и переходящий из одного режима в другой в зависимости от результатов испытания данных на уплотняемость. В ходе испытания сравнивают N-сегментное скользящее среднее числа битов, необходимых кодеру в режиме уплотнения для представления сегмента из фиксированного числа символом, и число битов, необходимых кодеру для представления сегмента в прозрачном режиме.
Ясно, что в соответствии с известными из техники способами решения о применении уплотнения к принимаемому сигналу обычно принимаются после предшествующей попытки уплотнения по меньшей мере части принятого сигнала для передачи испытательного сигнала и после определения эффекта уплотнения на этом испытательном сигнале, чтобы решить, следует ли передавать сигнал в уплотненной форме. Некоторые из недостатков, присущих этим известным из техники способам, включают необходимость осуществления различных операций уплотнения по меньшей мере части принятого сигнала, чтобы установить эффект уплотнения, и, следовательно, расходование ресурсов уплотнения, в частности, если впоследствии сигнал оказывается непригодным для уплотнения.
Кроме того, в современных уплотнителях возникает другая сложность вследствие того, что после уплотнения испытательного сигнала, который, как пояснено ранее, является по меньшей мере частью исходного сигнала (или всем исходным сигналом), и окончательного решения о том, что сигнал не следует передавать в уплотненной форме, в уплотнителе не предусмотрен способ его возращения к предшествующему состоянию (т.е. состоянию уплотнителя, предшествующему операции с испытательным сигналом). Соответственно, в таких случаях должны использоваться дополнительные ресурсы для дублирования и сохранения состояния уплотнителя до применения уплотнения к испытательному сигналу, позволяющие передавать сигнал в неуплотненной форме.
Таким образом, в настоящем изобретении преодолены указанные недостатки и предложен способ, позволяющий определять, может ли сигнал, который следует передать по каналу передачи, быть передан преимущественно в уплотненной форме.
Краткое изложение сущности изобретения
Соответственно, в основу изобретения положена задача создания средства, позволяющего определять, следует ли передавать сигналы в прозрачном режиме или режиме с уплотнением, и при работе в режиме с уплотнением определять соответствующий алгоритм уплотнения.
Одной из дополнительных задач настоящего изобретения является создание способов и машиночитаемых носителей для решения упомянутой выше задачи.
Другие задачи изобретения станут ясны после ознакомления с описанием изобретения.
В одном из вариантов осуществления настоящего изобретения предложен способ, позволяющий определять, следует ли передавать сигнал в уплотненной форме по каналу связи в сети связи, включающий стадии, на которых:
используют сигнал, который должен передаваться по каналу связи,
определяют, содержатся ли по меньшей мере в части сигнала данные с неслучайным распределением,
если определено, что по меньшей мере в части сигнала содержатся данные по меньшей мере с частично неслучайным распределением, применяют алгоритм уплотнения по меньшей мере к части сигнала, чтобы получить используемый сигнал в уплотненной форме, и
передают сигнал в уплотненной форме по каналу связи.
Термин "определяют, следует ли передавать сигнал в уплотненной форме" используется в описании, чтобы указать, следует ли применить алгоритм уплотнения к сигналу, и, если это так, т.е. такой алгоритм уплотнения следует применить, определяют тип алгоритм уплотнения для использования.
В одном из вариантов осуществления изобретения сетью связи является сеть с коммутацией пакетов, а по меньшей мере частью сигнала является по меньшей мере часть одного пакета.
В другом варианте осуществления на стадии, на которой определяют, содержатся ли по меньшей мере в части сигнала данные по меньшей мере с частично неслучайным распределением, применяют статистику суммарных величин по меньшей мере к части сигнала, что позволяет установить, имеют ли данные, содержащиеся по меньшей мере в этой части сигнала, случайное или неслучайное распределение.
Согласно другому варианту осуществления изобретения на стадии, на которой определяют, содержатся ли по меньшей мере в части сигнала данные по меньшей мере с частично неслучайным распределением, определяют, превышает ли распределение данных, содержащихся по меньшей мере в части сигнала, определенный порог неслучайного распределения. Более предпочтительно на стадии, на которой определяют, является ли распределение данных, содержащихся по меньшей мере в части сигнала, по меньшей мере частично неслучайным распределением, используют множество порогов неслучайного распределения, определяют, какие из этих порогов превышены в распределении данных, содержащихся по меньшей мере в части сигнала, и, исходя из превышенного порога(-ов), определяют алгоритм уплотнения для использования с целью уплотнения по меньшей мере части сигнала.
Специалисты в данной области техники учтут, что, хотя применение алгоритма уплотнения по меньшей мере к части сигнала осуществляют после того, как определено, что для распределения данных по меньшей мере в этой части сигнала характерна по меньшей мере некоторая степень неслучайного распределения, тем не менее, могут возникать случаи (хотя и редко), когда применимые для уплотнения сигналы не будут уплотнены в соответствии с настоящим изобретением, поскольку распределение данных в них согласно предложенному в изобретении способу считается случайным распределением, как, например, в противодействующем сигнале и т.п.
Всего лишь в нескольких случаях порог(-и), которые используются, чтобы определять, содержатся ли по меньшей мере в части сигнала данные с неслучайным распределением, являются предварительно установленными порогами, однако согласно одному из предпочтительных вариантов осуществления настоящего изобретения порог(-и) является/являются адаптивным порогом(-ами), которые изменяются в зависимости от доступных ресурсов, например, доступной полосой пропускания для передачи по меньшей мере части сигнала его адресату, доступных ресурсов обработки и т.п.
Хотя сигналом согласно настоящему изобретению предпочтительно является сигнал данных, например, компьютерные файлы и т.д., им также могут являться, например, сигналы различных типов, такие как речевой сигнал, видеосигнал и т.д. в форме пакетов, которые рассматриваются как сигналы данных.
В еще одном варианте осуществления изобретения на стадии, на которой определяют, содержатся ли по меньшей мере в части сигнала данные с неслучайным распределением:
подсчитывают число случаев, когда по меньшей мере в части сигнала содержится по меньшей мере один символ (или по меньшей мере одна комбинация символов) (например, сколько раз в полезной нагрузке данных по меньшей мере части сигнала встречается символ, отображающий букву "А"), и
если общее число случаев, когда по меньшей мере в части сигнала содержится по меньшей мере один символ, отвечающий предварительно установленному критерию, определяют, что по меньшей мере в части сигнала содержатся данные с неслучайным распределением.
Специалисты в данной области техники учтут, что в настоящем изобретении предусмотрен подсчет встречаемости определенного символа по меньшей мере в части сигнала, или встречаемости определенного числа (или каждого из) символов, которые содержатся по меньшей мере в части сигнала, или встречаемости одной или нескольких комбинаций из двух или более символов каждая, или любого сочетания из перечисленного, при этом все это далее именуется подсчетом того, сколько раз по меньшей мере один символ встречается по меньшей мере в части сигнала.
Общее число случаев, когда по меньшей мере один символ содержится по меньшей мере в части сигнала, предпочтительно считается отвечающим предварительно установленному критерию, если превышено пороговое отношение числа этих случаев, деленного на общее число символом, представляющих данные, содержащиеся по меньшей мере в части сигнала.
Подразумевается, что используемый далее термин "сеть связи с коммутацией пакетов" охватывает различные типы известных из техники сетей, таких как сети синхронной и асинхронной передачи данных, например, сети ATM, сети Ethernet, IP-сети, сети ретрансляции кадров, городские вычислительные сети (MAN), глобальные вычислительные сети (WAN), локальные вычислительные сети (LAN), пакетные сети SONET/SDH, сети беспроводной связи и т.п.
Согласно другому варианту осуществления изобретения предварительно установленный критерий зависит от того, какой алгоритм уплотнения будет использован для уплотнения по меньшей мере части сигнала, если сигнал содержит данные с неслучайным распределением.
Согласно еще одному варианту осуществления изобретения алгоритм уплотнения, который впоследствии используется для уплотнения по меньшей мере части цифрового сигнала, если он содержит данные с неслучайным распределением, выбирают из множества алгоритмов уплотнения, исходя из числа случаев, когда по меньшей мере один символ содержится по меньшей мере в этой одной части, например, исходя из разности между числом случаев, когда по меньшей мере в этой части сигнала содержится по меньшей мере один символ, и предварительно установленным критерием.
Используемый далее термин "алгоритм" означает различные способы обработки сигналов. Такие алгоритмы предусматривают передачу сигналов, такую как передачу с демодуляцией/повторной модуляцией, различные типы уплотнения с потерями или без потерь, уплотнение с переменной скоростью, транскодирование и т.п.
Согласно еще одному варианту осуществления изобретения предложено устройство, содержащее:
входной интерфейс, предназначенный для приема сигнала,
детектор, предназначенный для того, чтобы определять, содержатся ли по меньшей мере в части сигнала данные с неслучайным распределением,
уплотнитель, предназначенный для уплотнения по меньшей мере части сигнала, в которой содержатся данные с неслучайным распределением,
выходной интерфейс, предназначенный для пересылки принятого сигнала, по меньшей мере часть которого находится в уплотненной форме, соответствующему адресату.
Согласно другому варианту осуществления изобретения детектор определяет, содержит ли сигнал данные по меньшей мере с частично неслучайным распределением путем применения статистики суммарных величин по меньшей мере к части сигнала, чтобы определять, имеют ли содержащиеся в нем данные случайное или по меньшей мере частично неслучайное распределение по меньшей мере в этой части сигнала. В еще одном варианте осуществления изобретения детектор осуществляет подсчет числа случаев, когда по меньшей мере в части сигнала содержится по меньшей мере один символ (или по меньшей мере одна комбинация символов), и
если общее число случаев, когда по меньшей мере в части сигнала содержится по меньшей мере один символ, соответствует выбранному критерию, определяет, что по меньшей мере в части сигнала содержатся данные с неслучайным распределением.
Кроме того, детектор предпочтительно определяет, было ли превышено пороговое отношение числа случаев, когда по меньшей мере в части сигнала содержится определенный символ, и общего числа символов, отображающих содержащиеся в нем данные.
В еще одном из вариантов осуществления уплотнитель дополнительно предназначен для выбора и применения алгоритма уплотнения на основании информации, принимаемой от детектора.
Краткое описание чертежей
На фиг.1 показана блок-схема, иллюстрирующая один из примеров конструкции устройства уплотнения согласно одному из вариантов осуществления изобретения, и
на фиг.2 показана диаграмма, иллюстрирующая различие между случайным и неслучайным распределениями данных в сигналах, передаваемых по сети связи.
Подробное описание изобретения
Настоящее изобретение будет лучше понято после рассмотрения следующих далее подробных примеров в сочетании с чертежами.
Рассмотрим фиг.1, на которой проиллюстрирован один из примеров блок-схемы устройства уплотнения согласно одному из вариантов осуществления настоящего изобретения.
Допустим, что неуплотненный пакетный сигнал данных, передаваемый по сети с коммутацией пакетов, поступает во входной буфер 3 устройства 1 уплотнения, и для экономии ресурсов полосы пропускания в сети желательно по возможности уплотнить принятый сигнал.
Все принимаемые пакеты, каждый из которых содержит часть сигнала, пересылают детектору 5, в котором каждый из этих пакетов делят на порции, например, размером около 200 байтов. Компаратор 7 детектора 5 идентифицирует каждый из символов, содержащийся в полезной нагрузке пакета, после чего используют счетчик 9, чтобы определить число раз, когда каждый такой символ встречается в полезной нагрузке, например, число байтов, отображающих определенный символ, такой как буква. Блок 11 принятия решений сравнивает получаемые статистические данные с текущим известным порогом и решает, следует ли уплотнять эту порцию данных или передать ее в неуплотненной форме. Устройство 13 адаптации порога предоставляет пороговое значение, которое зависит от количества информации, накопленной во входном буфере 3. Переключатель 15 передает сигнал мультиплексору 19 в зависимости от принятого решения посредством уплотнителя 17 данных, который затем уплотняет порцию данных, или непосредственно мультиплексору 19 для передачи выходного сигнала, если уплотнение не требуется.
Специалисты в данной области техники учтут, что, хотя в этом не ограничивающем настоящее изобретение примере описано его осуществление применительно к каждому из пакетов независимо от предшествующего или последующего пакетов, тем не менее, такая же процедура с соответствующими изменениями может осуществляться применительно к группе из нескольких пакетов, и принимаемые решения будут зависеть от содержимого полезной нагрузки в группе пакетов.
Теперь допустим, что используется рассчитанный на L байтов буфер. В одном из вариантов осуществления изобретения для каждого из 256 возможных символов определяют общее число байтов, отображающих символ. Рассмотрим два из возможных вариантов использования получаемой таким способом информации. Согласно первому из них определяют число символов, для которых число отображающих байтов, включенных в буфер, превышает предварительно установленный порог. Если число символов превышает предварительно установленное число (в зависимости от размера L буфера), считается, что в буфере находится часть сигнала, которая имеет неслучайное распределение данных. Другим возможным вариантом является ранжирование символов по числу раз, когда они встречаются в буфере, суммирование числа раз, когда в буфере встречается число х наиболее частых символов (например, 25% наиболее частых символов), чтобы определить, превышает ли порог суммарный показатель встречаемости, нормализованный с учетом размера буфера. Специалисты в данной области техники учтут, что эти два варианта описаны лишь в качестве примеров, и возможно применение других типов более сложных методов проверки статистических гипотез и даже достижение более надежного детектирования.
Описанный механизм проиллюстрирован на фиг.2, на которой по вертикальной оси представлен суммарный показатель встречаемости числа х наиболее частых символов, ранжированный по частоте встречаемости в анализируемом блоке данных и деленный на общее число анализируемых символов. По горизонтальной оси отложено число х. Как показано на кривой "А", которая отображает применимые для уплотнения данные, число байтов, которые соответствуют относительно меньшему числу символов, является большим, чем это число при случайном распределении данных (кривая "В").
Если суммарный показатель встречаемости, нормализованный с учетом размера буфера, превышает порог, распределение данных в пакете считается неравномерным, и такой пакет может быть уплотнен с помощью любого применимого алгоритма уплотнения, который как таковой известен из техники, например, алгоритма Зива-Лемпеля, алгоритма прогнозирования по частичному совпадению или любого другого применимого алгоритма, известного из техники. Чтобы определить, является распределение данных, содержащихся по меньшей мере в части сигнала, по меньшей мере частично неслучайным распределением, предпочтительно используют несколько порогов неслучайного распределения и определяют, какой из этих порогов превышен в распределении данных, содержащихся по меньшей мере в части сигнала. На основании превышенных порогов можно определять, какой алгоритм уплотнения следует применить для уплотнения по меньшей мере части сигнала, например, чем больше неслучайное распределение данных, тем сильнее уплотнение, которое может к ним применяться.
После того, как выбран соответствующий алгоритм уплотнения, его применяют к пакету, чтобы тем самым уменьшить полосу пропускания, необходимую для пересылки этого пакета по каналу передачи его адресату. Затем уплотненный пакет поступает в устройство 11 пакетирования, которое формирует пакет для пересылки по каналу передачи.
Хотя в рассмотренном примере описана сеть коммутацией пакетов, подразумевается, что настоящее изобретение не ограничено такими сетями и с соответствующими изменениями также применимо в других сетях (например, сетях мультиплексной передачи с временным разделением (TDM)).
Подразумевается, что термины "случайное распределение" и "по меньшей мере частично неслучайное распределение", используемые в описании и формуле изобретения, предпочтительно означают эмпирический количественный критерий, определяемый путем применения соответствующего порога(-ов). Иными словами, вопрос, является ли распределение данных случайным или неслучайным (или частично неслучайным), по существу сводится к вопросу, превышает ли число раз, когда определенный символ или символы встречаются в сигнале, один или несколько порогов.
Подразумевается, что настоящее изобретение описано с помощью неограничивающих его подробных вариантов осуществления, которые приведены в качестве примера и не имеют целью ограничить объем изобретения. Подразумевается, что признаки и(или) операции, описанные применительно к одному варианту осуществления, могут использоваться в других вариантах осуществления, и что не все варианты осуществления содержат все признаки и(или) операции, проиллюстрированные на конкретной фигуре чертежей или описанные применительно к одному из вариантов осуществления. Специалисты в данной области техники смогут предложить разновидности описанных вариантов осуществления.
Следует отметить, что в некоторых из описанных вариантов осуществления предложен лучший вариант осуществления, предусмотренный авторами изобретения, и, соответственно, описаны устройство, операции или подробности устройства и операций, которые могут быть несущественны для изобретения и приведены в качестве примеров. Описанное устройство и операции могут быть заменены известными из техники эквивалентами, которые выполняют такую же функцию даже при отличии от устройства и операций, например, для выполнения по меньшей мере некоторых из функций, которые, как описано в настоящем изобретении, выполняет детектор, может применяться процессор. Соответственно, объем изобретения ограничен только признаками, охарактеризованными в формуле изобретения. При использовании далее в формуле изобретения термины "содержит", "включает", "имеет" и их производные означают "включает без ограничения".