УСТРОЙСТВО И СООТВЕТСТВУЮЩАЯ МЕТОДОЛОГИЯ ДЛЯ КОДИРОВАНИЯ И ДЕКОДИРОВАНИЯ ДАННЫХ ДЛЯ КОДА ЗАТИРАНИЯ Российский патент 2021 года по МПК H03M13/29 H03M13/37 

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

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

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

Искажение данных в средах для хранения данных может быть вызвано множеством причин, например, со стороны аппаратного обеспечения, сети, дисков, среды, облучения, электричества, программного обеспечения и так далее, все из которых приводят к ошибке в данных в клиентских приложениях. В современной среде данных, где упор делается все больше и больше на распределенные данные и приложения, проблема идет от более безопасных центров обработки данных (ЦОД), (data center, DC) к малым устройствам, поддерживающим технологию «Интернет вещей» (Internet of Things, IoT), и сети Интернет. Для уменьшения проблем с ошибками в данных ЦОД копируют данные на несколько ЦОД для обеспечения постоянной доступности копий данных. Однако копирование копий данных создает временные промежутки между копиями данных, приумножает количество данных, а также создает большое количество дополнительной работы для ЦОД с целью обеспечения возможности сохранения всех данных.

Включение кодов прямой коррекции ошибок (Forward Error Correction, FEC) существенно улучшило данную ситуацию в ЦОД при работе с избыточным массивом независимых дисков (Redundant Array of Inexpensive Disks, RAID). Однако существующий FEC–код Рида–Соломона и подобные FEC–коды не в достаточной степени подходят для работы с распределенными хранилищами данных при дальнейших нуждах в широко распределенном хранилище. В настоящее время стандартом хранения является использование систематического кода затирания, причем под систематическим кодом следует понимать случай, когда входные данные встроены в закодированные выходные данные, а с другой стороны, несистематический код относится к случаю, при котором выходные данные не содержат входные символы. Преобразование Мохетта по своей природе является несистематическим кодом и не обладает оптимальной производительностью во время рабочих режимов без затирания, а также не четко подходит к фреймворкам кода затирания для хранилища устаревших данных или поддерживающим код затирания кодовым фреймворкам, разработанным для библиотек системного кода затирания.

Преобразование Мохетта по своей природе является несистематическим кодом, и порции четности, или избыточные порции (паритетные порции, parity chunks), имеют больший размер (1+ε), чем соответствующая систематическая порция, где эпсилон ε > 0, делая так, что порции (m) четности содержат больше информации, чем порции данных. Позже можно увидеть, что это свойство m порций четности используют в современных центральных процессорах (ЦП) с целью уменьшения циклов ЦП в процессе декодирования, выравнивая пакеты m проекций четности при ε >> 0 в качестве основания для создания оптимальной производительности.

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

РАСКРЫТИЕ СУЩНОСТИ ИЗОБРЕТЕНИЯ

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

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

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

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

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

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

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

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

Фиг. 3 представляет собой пример преобразования Мохетта, кодирующего блок из трех строк с шестью пикселями в каждой строке в q=0 проекций, proj(1,0), в комбинации с проекциями, не являющимися q=0 проекциями, т.е. q=0 проекций proj(1,0) вместе с q≠0 проекций proj(–2,1), proj(2,1).

Фиг. 4 представляет собой пример декодирования с использованием примера кодирования на фиг. 3 вместе с процедурой на фиг. 2 без затирания.

Фиг. 5 представляет собой пример декодирования с использованием примера кодирования на фиг. 3 вместе с процедурой на фиг. 2 при отсутствии proj(1,0) для второй (2) строки и присутствии затирания для повторного построения отсутствующей строки в блоке.

Фиг. 6а представляет собой пример пиксельной конфигурации матрицы, где пиксели расположены строка за строкой для конфигурации матрицы, при размере данных b=64 и количестве k порций данных, которое также идентично количеству строк в матрице k=4.

Фиг. 6b представляет собой второй пример возможного выполнения пиксельной матрицы, в которой пиксели распределены по матрице столбец за столбцом, при размере данных b=64 и количестве k порций данных, которое также идентично количеству строк в матрице k=4.

Фиг. 7 представляет собой пример различных фаз операции декодирования. Начальной фазы 1–2 декодирования, устойчивой фазы 2–3 декодирования, при этом здесь отсутствует заключительная фаза (3 – конец) декодирования, даже когда это предусмотрено для данного примера конфигурации. Фазы отличаются по размеру при отображении в размерах реальных данных, т.е. 4 Кб или больше, делая начальную и заключительную фазы очень короткими по сравнению с устойчивой.

Фиг. 8 представляет собой иллюстративное графическое представление m порции четности, здесь P(2,1). Это представляет собой представление m проекции четности P(2,1) на том же виде, показывающее положения бинарного элемента и пикселя, показывая для верхней строки номер бинарного элемента от 1 до 22, а для нижней строки – сумму положений пикселей для заданного бинарного элемента, просуммированных по вертикали. Номера в матрице представляют собой номера положения пикселя, при этом топология пикселей может быть выполнена различными способами, однако здесь представлена простая построчная топология для иллюстрации того, каким образом выровненные m проекций четности могут работать для решения более одного (1) пикселя на итерацию из числа m проекций четности, таким образом, чтобы обеспечить возможность получения максимального ускорения при использовании векторизированного кода. Для упрощения этого, значение положения пикселя и идентификационный номер положения могут быть идентичными.

Фиг. 9 представляет собой пример выровненного пакета m порций четности, состоящего из 3 порций, выполненного с возможностью решения 2 пикселей на итерацию, при размере данных b=64 и количестве k порций данных, которое также идентично количеству строк в матрице k=4. M порций четности P(2,1), P(4,1), P(6,1) используется здесь для второго примера.

Фиг. 10 представляет собой пример пакета m порций четности после выполнения начальной фазы, как описано в таблице 1, где нуль указывает на то, что из бинарных элементов было вычтено значение пикселя, а результаты вставлены в матрицу с использованием преобразования Мохетта для декодирования. Начальная фаза завершается, когда каждая m порция четности решает корректную строку, заданную значением p m порции четности и номером строки при сортировке по размеру. Сортировка может быть выполнена по возрастанию или по убыванию исходя из предпочтений, однако в данном примере верхняя строка является самой высокой, а нижняя – самой низкой.

Фиг. 11а представляет собой пример начального этапа 14 итерации примера устойчивой фазы декодирования с использованием m порции четности P(4,1).

Фиг. 11b представляет собой пример начального этапа 15 итерации примера устойчивой фазы декодирования с использованием m порции четности P(6,1).

Фиг. 11c представляет собой пример начального этапа 16 итерации примера устойчивой фазы декодирования с использованием m порции четности P(2,1).

Фиг. 11d представляет собой пример начального этапа 17 итерации примера устойчивой фазы декодирования с использованием m порции четности P(4,1).

Фиг. 11e представляет собой пример начального этапа 18 итерации примера устойчивой фазы декодирования с использованием m порции четности P(6,1).

Фиг. 11f представляет собой пример начального этапа 19 итерации примера устойчивой фазы декодирования с использованием m порции четности P(2,1).

Фиг. 12 представляет собой пример пакета m порций четности в данном примере также после устойчивой фазы декодирования, дополнительно описанной в таблице 2, где нуль указывает на то, что из бинарных элементов было вычтено значение пикселя, а результаты вставлены в матрицу с использованием преобразования Мохетта для декодирования.

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

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

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

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

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

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

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

Потеря данных в любом приложении недопустима и это обуславливает потребность от ЦОД защищать данные путем копирования на другие хранилища или ЦОД, тем самым всегда имея копии данных. Это обеспечивает возможность реконструирования данных, если данные или хранилище потеряны по любым обстоятельствам. Однако копирование не является оптимальным при обращении с большим количеством данных, поскольку все данные должны быть полностью переданы и копированы, если узел потерян. Копирование также обуславливает необходимость в наличии различных версий данных в различных хранилищах, что делает обращение и поддержку очень сложными и трудоемкими для администратора. Кроме того, количество данных в среде для копирования, как правило, в 3–7 раз превышает исходные данные вследствие вышеуказанных потребностей в безопасности и наличии распределения данных по земному шару или между представительствами.

Введение технологий кодирования с затиранием, таких как технология Рида–Соломона, существенно улучшило ситуацию внутри ЦОД. В этих ситуациях копирование замещено на RAID, тем самым снижая потребность в емкости хранилища в 3–5 раза, в результате обеспечивая преимущества в части затрат, среды, обслуживания и безопасности внутри ЦОДов.

В существующих в настоящее время библиотеках кода затирания был установлен промышленный стандарт для задания различным параметрам настроек стандартного имени, упрощая интегрирование различных библиотек в приложения. Далее под k обозначено количество фрагментов данных или порций данных для проекций OPTFEC proj(1, 0), а также минимальное количество проекций для OPTFEC для повторного построения блока, и количество строк в OPTFEC–блоке. Кроме того, под m обозначено количество фрагментов четности или порций четности для проекций OPTFEC proj(pi, qi≠ 0), а также максимальное количество проекций, которые могут быть потеряны, но при этом по–прежнему обеспечивая возможность повторного построения или реконструирования блока данных. Более того, размер пакета = {bytes} или только b обозначает размер блока или размер файла, при задании размера матрицы на фиг. 6а и 6b, используемой при кодировании и декодировании данных, в соответствии с иллюстративными аспектами настоящих улучшений.

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

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

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

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

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

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

В соответствии с иллюстративными аспектами настоящих улучшений, для выдачи конкретного представления декодированных данных используется новая версия преобразования Мохетта. Далее термин «бинарный элемент» используется для обозначения элемента проекции в проекции преобразования Мохетта. Вкратце, преобразование Мохетта представляет собой линейное дискретное точное преобразование Радона, иными словами, набор l дискретных проекций, описывающий дискретное изображение f. Углы проекции выбраны из числа дискретных направлений φ_i=arctan(q_i/p_i), где нижний индекс i принимает целые значения, а p_i и q_i являются взаимно простыми, т.е. наибольший общий делитель составляет 1, GCD (p_i,q_i)=1. Одно преимущество данных алгоритмов заключается в том, что они используют только сложение и вычитание для операций кодирования и декодирования, тем самым минимизируя нагрузку на ЦП для операций и делая приложение быстрым. Решения в настоящем документе включают в себя посредством ссылки и, в частности, описание преобразования Мохетта в разделе 2, выбор проекций в разделе 3 и выбор бинарных элементов в разделе 4.

Первый пример для проекций (p,q) p1=(0,1), p2=(1,1), p3=(–1,1) показывает, что они хорошо подходят для базовой конфигурации Мохетта для целей хранения при обеспечении минимальных избыточных данных для каждой вычисленной проекции и имеет простой путь реконструирования. Решения в настоящем документе включают в себя полностью посредством ссылки и, в частности, описание преобразования Мохетта в разделе 2 и реконструирование, определяемое геометрией, в разделе 3. Если с другой стороны для операции декодирования требуется максимальная производительность, m проекций четности может быть выбрано для обеспечения большего эпсилон, ε >> 0. В зависимости от ЦП, подлежащего использованию, может быть использован максимальный ε и выровненные m проекций четности для функционирования в качестве пакета проекций четности.

Второй пример включает в себя конфигурацию, в которой декодируют два пикселя на итерацию вместо декодирования одного пикселя для каждой итерации из числа m проекций четности. В данном примере конфигураци кода затирания используются следующие параметры: Размер блока=128, Порции данных (k) = 4, Порции четности (m) = 3. Для базового случая соответствующие проекции представляют собой (p,q) p1=(0,1), p2=(1,1), p3=(–1,1), минимизируя эпсилон ε ≈ 0. При использовании конфигурации для повышенной производительности, для увеличения допускаются m порций четности, а эпсилон является ε >> 0. В случае решения минимум двух пикселей на итерацию m проекций четности соответствующие выровненные проекции четности представляют собой (p,q) p1=(2,1), p2=(4,1), p3=(6,1), где значение p выровненных m проекций четности увеличивается с p1 до p3 с шагом в 2 пикселя. Когда шаг составляет 5 пикселей исходя из увеличения ε или других соображений, пакет выровненных m порций четности содержит (p,q) p1=(5,1), p2=(10,1), p3=(15,1). В целях ясности, пакет выровненных m проекций четности представляет собой количество порций четности с различными значениями p, которое имеет минимальный устойчивый шаг пикселей больше чем один на итерацию во время устойчивой фазы операции декодирования. Шаг пикселя представляет собой количество пикселей, возможных для решения за итерацию.

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

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

Большее значение ε ускоряет декодирование до точки, но ε также может быть увеличен до точки, в которой аппаратные/программные ограничения делают невозможным дальнейшее ускорение. Кроме того, при использовании пакетов не идеально выровненных m проекций четности, декодеру требуется идентифицировать максимальное количество пикселей, возможных для решения для каждой итерации из числа m проекций четности, что может сделать декодер медленнее. Минимальное количество пикселей, которые могут быть решены пакетом идеально выровненных m проекций четности во время устойчивой фазы, представляет собой значение p шага приращения пикселя между проекциями четности. В зависимости от конфигурации и потерянных проекций данных, это может существенно отличаться до точки одного затирания (потеряна одна порция данных), где полная векторизация может иметь место для декодирования без каких–либо фаз, при этом всегда имеется только один пиксель для решения для каждого бинарного элемента из m проекций четности. Один конкретный случай затирания можно подробно увидеть в качестве примера на фиг. 5. В данном случае полностью векторизированное решение для одного затирания недоступно, когда несистематическое преобразование Мохетта не имеет каких–либо порций данных, а имеет лишь m порций четности для операций декодирования.

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

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

Оператор преобразования/проекции Мохетта определяется следующим образом:

Индексы суммирования P и Q соответствуют размеру блока данных, т.е. данные заданы представлением блока данных размера P x Q, a представляет собой номер, который будет указывать на конкретную линию, над которой центрируются элементы или пиксели. Применение оператора преобразования Мохетта к конкретному блоку данных дает сумму элементов или пикселей, которые отцентрированы около конкретной линии , причем конкретная линия может быть выведена из дельта–функции Кронекера если a=0 и 0 в противном случае. Далее a удаляют из переменной в , а проекция просто обозначается как (p_i, q_i). Приведенная выше формула (1) может быть использована для генерирования любой проекции с любым значением p и q. Число B сумм линий, также называемое числом бинарных элементов, на проекцию задается

.

В иллюстративных аспектах настоящих улучшений предусмотрено вычисление размера оптимального шага пикселя. Один способ нахождения оптимального шага пикселя описан ниже, где q=1, а все значения p являются положительными. В данном примере входными m порциями четности являются P(30,1), P(25,1), P(20,1), решающие три затирания.

1. Отсортировать m порций четности по их значениям p. Отсортированные значения p, 30, 25, 20;

2. Вычислить разницу между p для каждой пары отсортированных m порций четности. Минимальное значение данного вычисления также является минимально устойчивым шагом пикселя, который может быть использован. Разница между значениями p составляет 5, 5;

3. Вычислить коэффициент шага пикселя путем деления каждого значения p из отсортированных m порций четности на затирание, которое собирается решить порция. Например, здесь три затирания с самым высоким значением p будут решать самое высокое затирание. Затем также следует разделить предыдущее найденное значение на этапе 2 на минимальную разницу между значениями p. 30/(3 * 5) = 2, 25/(2 * 5)=2.5, 20/(1 * 5)=4; и

4. Вычислить оптимальный шаг пикселя путем нахождения коэффициента минимального шага пикселя из указанных выше m порций четности и умножить его на минимальный шаг пикселя, найденный ранее на этапе 2. Теперь он является максимальным устойчивым шагом пикселя, который может быть использован для m порций четности в данном примере. Оптимальный шаг пикселя вычисляется из минимальной разницы с этапа 2 и он умножается на минимальный коэффициент с этапа 4. Оптимальным шагом пикселя в данном примере является 5 * 2=10.

Если используются также отрицательные значения p, то это вычисление может быть выполнено таким же образом, что и для положительных. Значение m порций четности P(0,1) является уникальным и с ним необходимо работать отдельно при использовании указанного выше способа для нахождения оптимального шага пикселя из входных m порций четности.

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

Пример кодирования данных, описанный в настоящем документе, также обеспечивает возможность быстрого и эффективного с точки зрения вычислений декодирования данных, а также возможность высокоэффективного реконструирования ошибочных данных. Если во время декодирования происходят затирания, работу по декодированию упрощают меньше чем k затираний. Когда во время декодирования в режиме затирания присутствуют от 1 до k–1 строк, меньшее количество пикселей должно быть вычислено и скопировано с использованием m проекций proj(pi, q ≠ 0). Это обеспечивает возможность потребления меньшего количества циклов ЦП при декодировании, увеличивая производительность декодирования.

Если, с другой стороны, количество затираний ≥ k для k потерянных порций данных, декодирование выполняют так, как в стандартном несистематическом преобразовании Мохетта с использованием только m проекций proj(pi, q ≠ 0) для полной операции декодирования. Использование пакетов выровненных проекций ускоряет все режимы декодирования в систематическом или несистематическом режиме по сравнению с использованием пакета минимальной проекции, где ε является настолько малым, насколько это возможно. Операции декодирования с использованием пакетов выровненных проекций (OPTFEC) обеспечивают возможность оптимизации операций для современных ЦП, ППВМ (программируемых пользователем вентильных матриц) и ГП (графических процессоров).

Настоящие улучшения обеспечивают конкретный механизм как для кодирования, так и для декодирования данных, включающий конкретное применение двух типов проекций, proj(p_i =1,q_i =0) и proj(p_i, q ≠ 0). Эти проекции используются в конкретной комбинации для достижения высоко устойчивого кодирования данных. Пример кодирования данных, в соответствии с настоящими улучшениями, также обеспечивает возможность быстрого и эффективного с точки зрения вычислений декодирования данных, а также возможность высокоэффективного реконструирования ошибочных данных, если такие данные были выявлены. Настоящие улучшения обеспечивают механизмы, в которых сторона декодирования данных может выбирать конкретную схему декодирования для использования исходя из информации, предоставленной стороной кодирования, т.е. путем выполнения конкретной проверки закодированных данных. Сторона кодирования и сторона декодирования описаны ниже по отдельности.

В соответствии с первым иллюстративным аспектом настоящих улучшений, способ генерирования закодированных данных включает этап S1 получения данных в форме данных, отформатированных в соответствии с конкретными настройками, чтобы они содержали строки и столбцы. Способ также включает этап S2 создания, путем применения кодирующего преобразования к полученному блоку данных, набора проекций, proj (p_i, q_i), при этом набор проекций содержит первое количество проекций, proj (p_i=1, q_i=0), и второе количество проекций, proj (p_i, q_i≠0). Второе количество проекций, proj (p_i, q_i≠0), создается путем применения кодирующего преобразования Мохетта к блоку данных. Способ также включает этап S3 вывода созданного набора проекций для обеспечения возможности хранения данных в форме набора проекций.

Говоря несколько иначе, предусмотрен способ, который генерирует закодированные данные, такие как закодированные представления блоков данных. Исходная или оригинальная форма блока данных предоставляется в качестве входных данных и зависит от конкретного использованного форматирования. После получения блока данных способ создает набор проекций путем применения кодирующего преобразования к блоку данных. Кодирующее преобразование создает два конкретных набора проекций. Кодирующее преобразование основано на преобразовании Мохетта до такой степени, пока не будут созданы проекции, proj (p_i, q_i), основанные на блоке данных. Настоящие улучшения используют новое применение преобразования Мохетта для генерирования первого количества проекций, proj (p_i=1, q_i=0), тогда как второе количество проекций, proj (p_i, q_i≠0), создается путем применения традиционного кодирующего преобразования Мохетта к блоку данных. Количество вторых проекций, также называемое избыточными проекциями или m–проекциями, или m порциями четности, может быть любым количеством, которое может быть получено путем конкретизации индексов в proj (p_i, q_i≠0), например, (1, 1), (1, 2), (1, 3), (2, 1), (2, 2) и т.д. Таким образом, большое количество избыточных проекций может быть сгенерировано для того чтобы обезопасить данные. Конкретный этап S2 создания первого количества проекций, proj (p_i=1, q_i=0), включает, например, маппинг каждой строки блока данных с соответствующей проекцией, proj (p_i=1, q_i=0). Это создает проекции, которые несут ту же информацию, что и соответствующая строка. После создания первого и второго количества проекций, способ выдает созданный набор проекций для обеспечения возможности хранения данных в форме набора проекций или порций четности данных. Теперь, клиент, получающий доступ к закодированным данным, может декодировать данные в соответствии с предложенным механизмом декодирования, описанным ниже.

Проекции, proj (p_i=1, q_i=0), имеющие q=0, имеют свойства, отличающиеся от свойств проекций, имеющих q≠0, когда они не имеют дополнительной информации в строках. Таким образом, proj(1,0) также идентифицирована как q=0–проекция и очень похожа на порцию в стандартных приложениях, содержащую заголовок, который указывает на некоторые параметры для приложения, такие как, например, размер или некоторый другой параметр, которые могут быть использованы приложением для, например, идентификации, а также могут быть использованы вместе со средой преобразования Мохетта и полностью в нее интегрированы вместе с другими проекциями. Эти q=0–проекции или проекции порций данных, которые здесь идентифицированы как q=0 или proj(1,0) проекции, могут обрабатываться отдельно, поскольку они не несут какую–либо чрезмерную избыточную информацию, как q≠0 проекции. Таким образом, они требуют отдельного внимания в отношении ошибок в данных при использовании по отдельности, т.е. без наличия каких–либо q≠0 проекций во время операции декодирования. Это обусловлено тем фактом, что отсутствует способ верификации того, что конечный результат является корректным, без наличия q_i ≠0 проекций. Ошибка в отношении кодирования может быть выявлена путем верификации того, что все бинарные элементы были очищены во время декодирования и того, что каждый из бинарных элементов после декодирования равняется нулю (0), но без наличия q_i ≠0 проекции(й) во время декодирования это невозможно выполнить. Наличие бинарного элемента≠0 после декодирования обеспечивает указание на то, что во время кодирования данных произошла ошибка, и требуются новые q_i ≠0 проекции для обмена ложной проекции перед выполнением возобновленного декодирования и верификации декодированных данных.

Более того, q_i =0 проекции также имеют различные свойства по сравнению с q_i ≠0 проекциями, когда дело доходит до вычислений. Первое отличие заключается в том, что q=0 проекции имеют оригинальный размер, т.е. количество пикселей в q=0 проекциях является таким же, что и в оригинальных строках блока данных. Они также являются менее интенсивными с точки зрения вычислений, поскольку при выполнении кодирования и декодирования требуется меньшее количество вычислений. Эти свойства обеспечивают пониженные вычислительные затраты как во время кодирования, так и во время декодирования, и, как следствие, делают быстрее предложенный механизм кодирования, называемый OPTFEC в настоящем документе. Однако способ также создает второе количество проекций, proj (p_i, q_i≠0). Это может быть выполнено путем применения кодирующего преобразования Мохетта к блоку данных. Второе количество проекций обеспечивает избыточные проекции, которые используются для декодирования блока данных, если по меньшей мере одна из первого набора проекций содержит затирания или была ошибочно закодирована. Таким образом, может быть создано второе количество проекций, с q_i ≠0 путем применения традиционного преобразования Мохетта к блоку данных. В конце, различные проекции вместе обеспечивают конкретное представление закодированных данных, что обеспечивает высокоэффективное декодирование, при котором затирание данных или ошибочно закодированных данных может быть оперативно, т.е. с уменьшенным количеством вычислений, корректно реконструировано.

На фиг. 1 подробно изображен пример, в котором используется процедура кодирования, в соответствии с настоящими улучшениями. На этапе 100 принимают настройки из приложения вместе с настройками для способа, т.е. OPTFEC. Настройки используют для установки кода затирания на производительность, степень избыточности и устойчивость, которые были запрошены приложением и пользователем. На этапе 110 код затирания принимает входные данные, подлежащие преобразованию в k+m проекций. Входные данные и настройки с этапа 100 и этапа 110 подают в интерфейс кодера на этапе 120. На этапе 130 входные данные форматируют в соответствии с настройками, заданными на этапе 100, тем самым создавая количество k строк данных и количество столбцов, вычисленное как: Столбцы=размер блока/строки. На этапе 140 имеет место кодирование или преобразование данных для создания количества k q_i=0, т.е. proj(1,0), проекций и количества m избыточных проекций q≠0, т.е. proj(p_i, q≠ 0). Для q_i=0 проекций не предусмотрено стандартных бинарных элементов, в соответствии с преобразованием Мохетта. Вместо этого в качестве проекции сохраняют целую строку. Это более подробно описано при описании фиг. 3.

Созданные проекции имеют различные размеры в зависимости от количества строк и угла проекции для заданного блока и проекций. На этапе 150 различные проекции, имеющие qi=0 и q_i ≠0, идентифицируют таким образом, который подходит для поздней передачи на приложение или клиенту. На этапе 150 закодированные данные отправляют в виде выходных данных от кодера для хранения приложением на предпочтительном внутреннем буфере, где k=proj(1,0) и m=proj(p_i,q≠ 0) проекциям.

Ниже представлено подробное описание стороны декодирования, в соответствии с настоящими улучшениями. Способ декодирования данных использует режим избыточного декодирования. Способ включает этап S10 получения настроек. Настройки содержат количество k фрагментов данных и, при необходимости, количество m фрагментов четности вместе с информацией о том, активен ли режим поддержки кода затирания. Кроме того, настройки могут содержать размер блока или размер пакета b, размер матрицы и информацию о входном файле от приложения, подлежащего кодированию. Как будет ясно специалисту в данной области техники, могут быть включены другие параметры. Способ также включает этап S20 получения закодированных данных. Закодированные данные кодируют путем применения кодирующего преобразования к блоку данных, отформатированных в соответствии с настройками, при этом закодированные данные содержат набор проекций, proj(p_i, q_i), причем набор содержит первое количество проекций, proj (p_i=1, q_i=0), и второе количество проекций, proj(p_i, q_i≠0). Способ также включает этап S30 проверки того, равно ли первое количество проекций, proj (p_i=1, q_i=0), количеству k фрагментов данных. На этапе S40 способ выбирает, исходя из проверки, режим декодирования для использования при декодировании данных, причем режим декодирования представляет собой режим декодирования без затирания или режим декодирования с затиранием. Способ также включает этап S50 декодирования данных с использованием выбранного режима декодирования для реконструирования или воссоздания блока данных.

Режим избыточного декодирования, описанный в настоящем документе, включает первый режим декодирования, который представляет собой режим декодирования без затирания, и второй режим декодирования, который представляет собой режим декодирования с затиранием. Предложенный способ включает подэтапы, т.е. этапы S10–S40, для определения того, какой из режимов двойного декодирования следует использовать для конкретных закодированных данных. Затем способ использует определенный режим декодирования для декодирования данных. Сначала способ получает настройки, использованные при кодировании данных. Настройки могут быть получены в виде части информации, полученной при извлечении закодированных данных. Настройки также могут представлять собой заданные настройки или полученные некоторым другим образом без выхода за рамки объема настоящих улучшений. Настройки в целом содержат информацию по меньшей мере о количестве k фрагментов данных, но также могут содержать количество m фрагментов четности, а также размер блока или размер пакета закодированных данных. Размер блока может быть использован для определения количества столбцов или количества строк в блоке данных исходя из отношения: Столбцы=размер блока/строки. Здесь, количество k обозначает количество фрагментов данных или порций данных для proj(1,0) проекций, а также оно обеспечивает меру для минимального количества проекций, необходимых для обеспечения возможности повторного построения блока. Значение k также может обозначать количество строк в блоке OPTFEC. Количество m, относительно вышеуказанного, обозначает количество фрагментов четности для OPTFEC proj(p_i, q_i≠ 0) проекций и конкретизирует максимальное количество проекций, которые могут быть утеряны, при этом все еще обеспечивая возможность повторного построения или реконструирования блока данных в способе, т.е. оно обеспечивает меру избыточности системы. Из соображений ясности, для обеспечения возможности повторного построения или реконструирования исходного блока данных, необходимо общее количество k проекций. Эти k проекций не должны быть k исходными proj(1,0) проекциями, а могут быть комбинацией конкретного количества исходных proj(1,0) проекций и конкретного количества proj(p_i, q_i≠ 0) проекций. Для простоты рассмотрим случай, когда k=4 и m=8, здесь 8 проекций могут быть утеряны или стерты, а реконструирование все еще возможно, но если с другой стороны все или поднабор k исходных proj(1,0) проекций утеряны, реконструирование может быть выполнено путем использования соответствующего набора или поднабора m proj(p_i, q_i≠ 0) проекций. Таким образом, настоящие улучшения обеспечивают широкий ряд возможностей комбинирования k и m проекций для реконструирования ошибочного блока данных.

После получения настроек способ получает или принимает закодированные данные. Данные могут быть закодированы так, как описано выше в отношении способа генерирования закодированных данных и, таким образом, содержат набор проекций. Полученный или принятый набор проекций содержит два различных набора проекций, из которых первый содержит первое количество проекций, proj (p_i=1, q_i=0), а второй содержит второе количество проекций, proj(p_i, q_i≠0). Способ проверяет то, равняется ли полученное количество первых проекций количеству k, полученному с настройками. Исходя из того, справедливо ли равенство или нет, способ выбирает конкретный режим декодирования для использования при декодировании данных. Например, способ включает этап S40 выбора режима декодирования путем выбора режима декодирования без затирания, если первое количество проекций, proj (p_i=1, q_i=0), равняется количеству k фрагментов данных. Этап (S40) выбора режима декодирования также может включать выбор режима декодирования с затиранием, если первое количество проекций, proj (p_i=1, q_i=0), меньше чем количество k фрагментов данных.

В качестве примера, иллюстративный способ также включает этап S50 декодирования данных путем использования режима декодирования с затиранием, включающего еще один этап S51 контроля того, является ли набор полученных проекций Мохетта, proj (p_i, q_i), достаточным для декодирования блока данных. Например, способ на этапе S51 контроля также может включать определение того, является полученное первое количество проекций, proj (p_i=1, q_i=0), плюс полученное второе количество проекций, proj(p_i, q_i≠0), равным или больше чем количество строк в блоке данных.

В одном иллюстративном аспекте способ также включает этап запроса дополнительных проекций Мохетта proj(p_j,q_j), если полученное первое количество проекций, proj (p_i=1, q_i=0), плюс полученное второе количество проекций, proj(p_i, q_i≠0), меньше чем количество строк в блоке данных. Дополнительные проекции Мохетта proj(p_j,q_j) отличаются от первого количества проекций, proj (p_i=1, q_i=0), и второго количества проекций, proj(p_i, q_i≠0). В этом иллюстративном аспекте способ может декодировать блок данных путем использования первого количества проекций, proj (p_i=1, q_i=0), второго количества проекций, proj(p_i, q_i≠0), и необходимых дополнительных проекций Мохетта proj(p_j,q_j).

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

Способ также может реконструировать закодированные данные, содержащие затирание, без затирания путем использования по меньшей мере одной из полученного второго количества проекций, proj(p_i, q_i≠0). То есть способ может реконструировать ошибочно закодированные данные, т.е. блок данных, путем использования избыточной или чрезмерной информации, содержащейся в полученном втором количестве проекций, proj(p_i, q_i≠0). Это второе количество проекций содержит избыточную или чрезмерную информацию, что является причиной того, что в настоящем документе они называются избыточными проекциями.

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

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

На этапе 210 способ выполняет проверку для определения того, равняется ли количество proj(1,0) проекций настройке k, принятой на этапе 200. Если количество proj(1,0) проекций равняется k, то эти проекции, proj(1,0), могут быть использованы для повторного построения или реконструирования блока непосредственно на этапе 270. Это называется режимом без затирания. Если количество проекций, proj(1,0), меньше чем k, то требуется операция двойного декодирования, т.е. режим декодирования с затиранием. Эти два режима работы, режим без затирания и режим с затиранием, также называются режимом двойной работы.

На этапе 270 способ повторно строит блок с использованием proj(1,0) проекций, принятых с этапа 210. На этапе 220 способ тестирует, является ли достаточным количество принятых проекций для повторного построения блока или требуется вызов большего количества проекций. Если m+k ≥ строк, то имеется достаточно доступных проекций для выполнения декодирования для воссоздания или реконструирования исходных данных. Если m+k меньше чем количество строк, то отсутствует достаточное количество доступных проекций для реконструирования исходных данных. Следовательно, способ может запросить большее количество проекций на этапе 230 путем, например, отправки сигнала приложению. Из соображений ясности, для обеспечения возможности повторного построения или реконструирования исходного блока данных, необходимо общее количество k проекций. Эти k проекций не должны быть k исходными proj(1,0) проекциями, а могут быть комбинацией конкретного количества исходных proj(1,0) проекций и конкретного количества proj(p_i, q_i≠ 0) проекций. Для простоты рассмотрим случай, когда k=4 и m=8, здесь 8 проекций могут быть утеряны или стерты, а реконструирование все еще возможно, но если с другой стороны все k исходных proj(1,0) проекций утеряны, реконструирование может быть выполнено путем использования m proj(p_i, q_i≠ 0) проекций. Таким образом, настоящие улучшения обеспечивают широкий ряд возможностей комбинирования k и m проекций для реконструирования ошибочного блока данных. Если такая комбинация в данный момент отсутствует, то может быть отправлен сигнал для запроса дополнительных проекций. Эти дополнительные проекции могут, например, представлять собой proj(p_i, q_i≠ 0) проекции с более высокими значениями p_i и q_i. На этапе 230 помещают запрос на то, доступно ли большее количество избыточных проекций для выполнения повторного построения. Если большее количество проекций недоступно, то на этапе 250 приложению может быть выдано сообщение об ошибке. На этапе 240 выполняют декодирование принятых проекций для воссоздания исходных данных. На этапе 260 проверяют выходные данные с этапа 240 для верификации того, что выходные данные являются корректными. Если бинарные элементы=0, то данные являются корректными и их отправляют на этап 280. Если с другой стороны не все бинарные элементы равны 0, то на этапе 230 отправляют запрос на большее количество проекций. На этапе 280 выполняют вывод повторно построенных или реконструированных данных приложению/клиенту. Здесь также может быть выполнено выравнивание для корректного представления данных приложению/клиенту.

Фиг. 3 представляет собой пример OPTFEC–кодирования данных, в соответствии с настоящими улучшениями. На фиг. 3 данные форматированы при настройках k=3 m=2 и размере блока=18. На этапе 300 входные данные форматируют в блок, в соответствии с заданными настройками. На этапе 310 блок используют для генерирования проекций, имеющих q=0. Поскольку k=3, получают три проекции proj(1,0), по одной для каждой из строк 1–3, а управление пикселями в каждой строке рассматривают в качестве традиционных сумм пикселей в бинарных элементах, как и в проекциях, имеющих q≠0. На этапе 320 и этапе 330 получают две избыточные проекции, когда в данном примере входные настройки указывают, что m=2. Из настройки OPTFEC, установленной приложением и указывающей на то, что должны быть получены proj(2,1) и proj(–2,1), создают proj(2,1) на этапе 320 и proj(–2,1) на этапе 330. На этапе 340 отображают все проекции, демонстрирующие то, что m+k=5 и то, что proj(2,1) и proj(–2,1) на 4 бинарных элемента длиннее чем соответствующая proj(1,0). Здесь получают общее количество из 5 проекций, три (3) для q=0 и две (2) для избыточности q≠0, в соответствии с входным требованием k=3 m=2.

Фиг. 4 представляет собой пример декодирования блока с использованием проекций proj(1,0), в соответствии с фиг. 2. В данном примере общее количество проекций, имеющих proj(1,0), равную входной настройке k, также соответствуют количеству строк в блоке, подлежащему повторному построению. На этапе 400 выдают пустой блок, соответствующий заданным настройкам на этапе 100 с фиг. 1 для кодирования данных. В данном примере k=3 и m=2 при размере блока=18 и заданных 3 строках и 6 пикселях в каждой строке. В соответствии со способом на фиг. 2, количество проекций, имеющих q=0, равно k. Таким образом, следующим этапом является построение блока. Для проекций, имеющих q=0, p представляет собой строку, которая соответствует тому месту, куда должны быть вставлены данные. Этап 410 отображает вставку proj(1,0) в строку один, этап 420 отображает вставку proj(1,0) для строки два в строку два, а этап 430 отображает proj(1,0) для строки три (3) в строку номер три, выполняя повторное построение блока. На этапе 440 показан полностью повторно построенный блок, имеющий 3 строки, повторно построенные с использованием трех проекций, имеющих q=0.

На фиг. 5 изображено повторное построение блока при наличии затирания и при наличии потери одной строки r2, которая подлежит повторному построению с использованием проекции, не имеющей q=0. Приложение обеспечивает 3 проекции для затирания для повторного построения блока при заданных настройках k=3 и m=2 при размере блока=18. На фиг. 2 на этапе 210 определяют то, является ли количество проекций, имеющих q=0, меньше чем k. В данном случае количество проекций, имеющих q=0, не меньше чем k. Таким образом, способ переходит к этапу 220, на котором определяют то, что m+k=3, что говорит о том, что декодирование на этапе 240 на фиг. 2 возможно. Далее описан подробный пример того, каким образом выполняют это декодирование с затиранием с проекциями proj(1,0), proj(–2,1). На этапе 500 выдают пустой блок, соответствующий заданным настройкам на этапе 100 с фиг. 1 для кодирования данных. В данном примере k=3 и m=2 при размере блока=18 и (3 строки и 6 пикселей в каждой строке r1, r2, r3). На этапе 510 proj(1,0) вставляют в строку один (r1), а на этапе 520 проекцию proj(1,0), соответствующую строке три (3), вставляют в строку номер три (r3). Строка два (r2) является пустой, а для декодирования требуется третья проекция proj(–2,1). На этапе 530 вводят проекцию proj(–2,1) и из этих бинарных элементов выполняют вычитание уже заполненных пикселей для повторного построения строки два (r2). На этапе 530 S1, с использованием проекции proj(–2,1), уже заполненный пиксель составляет 7 и путем вычитания этого пикселя из первого бинарного элемента создают 0. То есть 7–7=0. На этапе 530 S2 проекция составляет 4 из уже присутствующих пикселей и это затем дает 4 из бинарного элемента проекций минус 4 из присутствующих в блоке проекций, и их вычитание дает нуль, 4–4=0. S3–S10 с использованием той же процедуры в результате дают: 11–2=9, 2–1=1, 14–2–9=3, 16–3–8=5, 12–5=7, 11–7=4, 4–4=0, 3–3=0, давая выходные данные из декодирования, показанного на этапе S10, т.е. [ 0 0 9 1 3 5 7 4 0 0]. Для заданной проекции proj(–2,1) при k=2, m=2 и размере блока=18, пиксели 3–8 являются теми пикселями, которые решают r2=(9, 1, 3, 5, 7, 4). После этой операции декодирования блок реконструируют с использованием декодирования Мохетта на этапе 540.

В соответствии с иллюстративным аспектом, способ может быть дополнен циклическим избыточным контролем (CRC), выполняемым на исходном или оригинальном блоке данных. Обеспечение того, чтобы исходный блок данных не содержал порченные данные, увеличивает эффективность способа, причем данные подвергаются преобразованию Мохетта для получения множества проекций преобразования Мохетта (p_i,q_i). Таким образом, в иллюстративных аспектах способ дополнительно включает выполнение CRC на исходных данных, и способ применяет преобразование Мохета к блоку данных только если сумма CRC корректна. Этим обеспечивается то, что клиент не должен выполнять декодирование Мохетта на данных, если данные испорчены, тем самым увеличивая эффективность.

Способ также может быть дополнен потоковыми SIMD–расширениями (SSE) для ускорения операций кодирования и декодирования. В данном варианте реализации также могут использоваться программируемые аппаратные устройства для ускорения операции кодирования и декодирования, такие как программируемая пользователем вентильная матрица (ППВМ). После выравнивания присутствующих пакетов вычисляемых проекций может быть создан очень эффективный SSE–ускоренный векторизированный код, который существенно уменьшает количество циклов ЦП, необходимых для процесса декодирования, при наличии затирания. Это же справедливо для реализации ППВМ или графического процессора (ГП), когда даже большее количество ядер могут работать параллельно для одновременного решения задачи декодирования при наличии затирания.

Далее представлены примеры пакета выровненной m порции четности с использованием следующих конфигурационных настроек для операций кодирования и декодирования. Конфигурация кодирования: Размер блока=64, Порции данных (k) = 4, Порции четности (m) = 3, проекции четности (p,q) p1=(2,1), p2=(4,1), p3=(6,1)

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

Декодирование: Порция данных для строк 1,2 и 4 потеряна и операция находится в режиме затирания, при этом используются следующие m проекции четности p1=(2,1), p2=(4,1), p3=(6,1), и k порция данных для строки 3 должна быть использована для повторного построения данных.

В таблице 1 показаны первые 13 этапов начальной фазы (неустойчивой) операции декодирования, где 3 k порций данных потеряны и 3 m порций четности использованы для замещения потерянных порций данных во время операции декодирования.

Таблица 1 Начальная фаза (неустойчивая)

Этап Проекция Положение/
Пиксели Решенная строка Верно/
Неверно 1 P(2,1) 1 и 2 1 Н 2 P(4,1) 3 и 4 1 Н 3 P(6,1) 5 и 6 1 В 4 P(2,1) 17 и 18 2 Н 5 P(4,1) Нет – Н 6 P(6,1) 7 и 8 1 В 7 P(2,1) 19 и 20 2 Н 8 P(4,1) Нет – Н 9 P(6,1) 9 и 10 1 В 10 P(2,1) Нет – Н 11 P(4,1) 21 и 22 2 В 12 P(6,1) 11 и 12 1 В 13 P(2,1) 49 и 50 4 В

Итерация, за которую выполняется каждая m порция четности, здесь составляет порядка P(2,1), P(4,1), P(6,1) и в таблице показан столбец один в первом этапе итерации. В столбце два использовалась m порция четности, в столбце три – решенные пиксели, в столбце 4 – строка, к которой принадлежат решенные пиксели, и в столбце 5, если для решения приведена корректная строка для использованной m проекции четности во время этого этапа итерации, указывается Верно или Неверно. Конец начальной фазы, указывая В или Н в столбце 5 таблицы 1, наступает, когда каждая m порция четности решает корректную строку, заданную значением p m порции четности и номером строки при сортировке по размеру. Это указано в таблице 1 на этапах 11, 12 и 13. Сортировка может быть выполнена по возрастанию или по убыванию в зависимости от предпочтений, однако в данном примере верхняя строка является самой высокой, а нижняя – самой низкой.

Эту начальную (неустойчивую) фазу характеризует то, что, как показано в таблице 1, не все итерации будут решать пиксели, как это происходит на этапах 5, 8 и 10. Для идеальной ситуации, как на более поздней устойчивой фазе, описанной ниже, количество выровненных пикселей, заданное конфигурацией, может быть решено на каждой итерации.

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

В таблице 2 показаны операции декодирования во время устойчивой фазы, решая в данном примере количество выровненных пикселей на этап итерации 14–19.

Таблица 2 для итераций устойчивой фазы

Этап Проекция Положение/Пиксели Решенная строка Верно/Неверно 14 P(4,1) 23 и 24 2 В 15 P(6,1) 13 и 14 1 В 16 P(2,1) 51 и 52 4 В 17 P(4,1) 25 и 26 2 В 18 P(6,1) 15 и 16 1 В 19 P(2,1) 53 и 54 4 В

При сравнении таблицы 1 с таблицей 2, столбец 5 Верно/Неверно в таблице 2 является устойчивым, т.е. всегда В, а использованная m порция четности в итерации решает корректную строку в матрице, каждый раз делая операцию декодирования очень эффективной и простой. На фиг. 7 устойчивая фаза между 2 и 3 для второго примера итерации за количество m порций четности иллюстрирует то, что она является устойчивой фазой, где каждая итерация или этап решает минимум выровненное количество пикселей, а отсортированные m порций четности решают отсортированную корректную строку.

Далее будет разъяснено кодирование/декодирование множества пикселей. В этих разъяснениях решения с множеством пикселей на итерацию используют пакеты выровненных m проекций четности. На фиг. 8 иллюстративная схема m порции четности P(2,1) изображает расположение пикселей в зависимости от схемы матрицы, как описано выше в отношении фиг. 6a, фиг. 6b и идентификационного номера бинарного элемента, и фактического бинарного элемента. В верхней строке указан идентификационный номер бинарного элемента слева направо, начиная с 1 и заканчивая 22. Ниже строки с идентификационным номером бинарного элемента находится представление m порции четности P(2,1), где каждая строка в матрице перемещена на два шага вправо исходя из значения p в m порции четности P(2,1). После этого, бинарные элементы вычисляют путем суммирования каждого столбца с идентификационным номером бинарного элемента вниз, показанные в виде строки суммы бинарных элементов с идентификационным номером бинарного элемента от 1 до 22. Идентификационные номера 1 и 2 имеют свойства, отличающиеся от идентификационных номеров 3–20 бинарного элемента, и этот паттерн повторяется для идентификационных номеров 21 и 22 бинарного элемента. Первые 2 и последние 2 идентификационных номера бинарного элемента свободны и не зависят от любой другой k порции данных или m порции четности. Эти идентификационные номера бинарного элемента решаются сами по себе. Преимущественно, данный признак обеспечивает возможность прямой передачи данных от этого положения пикселя непосредственно в матрицу данных. В данном случае значения в этих положениях пикселей, 1 и 2, и 63 и 64, непосредственно передаются в матрицу решений данных. Когда эти данные передаются в матрицу решений данных, каждая m порция четности должна быть обновлена. В данном примере для фиг. 8 информацию по пикселям 1, 2, 63 и 64 обновляют путем вычитания информации в пикселях 1, 2, 63 и 64 из соответствующего положения пикселя в каждом бинарном элементе, содержащем эти положения пикселя, для других m порций четности.

Фиг. 9 представляет собой графическое представление примера на фиг. 8. В этом примере пакет m порций четности выровнен для решения минимум двух пикселей на итерацию в зависимости от количества затираний и порции данных или m порции четности, которая была утеряна. Как показано на фиг. 8, здесь P(2,1) содержит 2+2 свободных пикселей, P(4,1) содержит 4+4 свободных пикселей, а P(6,1) содержит 6+6 свободных пикселей. Соответствующие графические представления m порции четности переместили строки вправо, заданные значением p в m порции четности, как разъяснено подробно на фиг. 8. Для отрицательного значения p в данном примере строки перемещены влево на значение p в m порции четности, как подробно разъяснено на фиг. 8. Пакеты выровненных m проекций четности для решения множества пикселей на итерацию за каждую m порцию четности во время операции декодирования могут быть установлены на использование как всех положительных значений p, положительных и отрицательных, так и всех отрицательных, где значение p минимальных абсолютных m порций четности будет обозначать максимальное количество пикселей, которые могут быть решены во время устойчивой фазы, с тем же количеством пикселей, решаемых за итерацию, при условии, что m порций четности с минимальными значениями используются для операции декодирования.

Статус пакета m порций четности во втором примере представлен на фиг. 10, на которой изображены данные после завершения начальной фазы. Это также показано в таблице 1. Здесь нули представляют уже решенные положения пикселей, а m проекция четности P(4,1) содержит положения двух свободных пикселей 23 и 24.

Фиг. 11а представляет собой статус после выполнения этапа 14 из таблицы 2 для решения пикселей 23 и 24, и уменьшение каждого бинарного элемента в других m проекциях четности для решенных пикселей. Как будет понятно, данный этап решает пиксели 23 и 24 и делает свободными два пикселя в положениях 13 и 14 пикселей в m порции четности P(6,1), которые теперь могут быть решены с использованием той же процедуры. Описанная процедура перемещается слева направо, однако процедура также может перемещаться справа налево, или перемещаться из двух направлений одновременно без выхода за пределы объема настоящих улучшений. Таким образом, ориентация матрицы и направление решения являются полностью гибкими.

На фиг. 11b положения пикселей 13 и 14, которые соединены с верхней строкой, решаются m проекцией четности с самым высоким значением p, как описано выше со ссылкой на этап 15 в таблице 1. Этап 16 в таблице 1 соответствует фиг. 11С, где m проекция четности, имеющая самое низкое значение p P(2,1), решает положения пикселей 51 и 52, находящихся в нижней строке матрицы. На фиг. 11d используется такая же процедура для решения положений пикселей 25 и 26, а фиг. 11е представляет собой решение для положений пикселей 15 и 16 для данного второго примера. На фиг. 11f используется процедура слева направо для решения положений пикселей 53 и 54. Все пиксели в этой устойчивой фазе решаются корректной m порцией четности, а также устойчивые базовые или минимальные положения пикселей задаются минимальным абсолютным значением p, используемым в итерации.

Фиг. 12 представляет собой пакет m проекций четности после решения всех положений пикселей. Если все бинарные элементы не равны нулю к концу операции декодирования, имеет место ошибка и операция декодирования не была успешной, или заданные порции содержали ошибки.

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

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

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

В иллюстративных аспектах настоящие улучшения также включают устройство 100 для генерирования закодированных данных. Устройство 100 выполнено с возможностью получения данных в форме блока данных, отформатированного в соответствии с конкретными настройками так, чтобы он содержал строки и столбцы. Устройство 100 также выполнено с возможностью создания, путем применения кодирующего преобразования к полученному блоку данных, набора проекций, proj (p_i, q_i), при этом набор содержит первое количество проекций, proj (p_i=1, q_i=0), и второе количество проекций, proj (p_i, q_i≠0), причем второе количество проекций proj (p_i, q_i≠0) создается путем применения кодирующего преобразования Мохетта к блоку данных. Кроме того, устройство 100 выполнено с возможностью вывода созданного набора проекций Мохетта для обеспечения возможности хранения данных в форме проекций Мохетта.

Устройство 100 также может быть выполнено с возможностью создания набора проекций, proj (p_i, q_i), и может быть выполнено с возможностью создания первого количества проекций, proj (p_i=1, q_i=0), путем маппинга каждой строки с соответствующей проекцией, proj (p_i=1, q_i=0), для создания проекций, несущих ту же информацию, что и соответствующая строка.

В другом варианте реализации устройства предусмотрено устройство 100, которое выполнено с возможностью создания набора проекций, proj (p_i, q_i), и может быть выполнено с возможностью создания второго количества проекций proj (p_i, q_i≠0) путем применения кодирующего преобразования Мохетта к блоку данных, при этом второе количество проекций обеспечивает избыточные проекции для использования с целью декодирования блока данных, если по меньшей мере одна из первого набора проекций содержит затирание или была ошибочно закодирована.

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

Устройство 100 также может содержать схему 130 связи. Схема 130 связи может содержать функции для проводной и/или беспроводной связи с другими устройствами в сети. В конкретном примере схема 130 связи может быть основана на радиосхеме для связи с одним или более других узлов, в том числе передачи и/или приема информации. Однако в равной степени возможна проводная связь, т.е. обмен данными по проводной сети. Схема 130 связи может быть соединена с процессором 110 и/или памятью 120. Схема 130 связи может быть соединена с аппаратной схемой 110. В качестве примера, схема 130 связи может содержать любое из следующего: приемник, передатчик, приемо–передатчик, схему ввода/вывода, порт(ы) ввода и/или порт(ы) вывода.

Устройство 200 может быть выполнено с возможностью декодирования данных путем использования режима избыточного декодирования. Устройство 200 выполнено с возможностью получения настроек, которые содержат количество k фрагментов данных и количество m фрагментов четности. Настройки также могут содержать размер блока, размер пакета закодированных данных. Устройство 200 также выполнено с возможностью получения закодированных данных, которые были закодированы путем применения кодирующего преобразования Мохетта к блоку данных, отформатированных в соответствии с настройками. Закодированные данные содержат набор проекций Мохетта, proj (p_i, q_i), и набор содержит первое количество проекций, proj (p_i=1, q_i=0), и второе количество проекций, proj(p_i, q_i≠0). Устройство 200 также выполнено с возможностью осуществления проверки того, равно ли первое количество проекций, proj (p_i=1, q_i=0), количеству k фрагментов данных. Устройство 200 также выполнено с возможностью выбора, исходя из проверки, режима декодирования для использования при декодировании данных, причем режим декодирования представляет собой режим декодирования без затирания или режим декодирования с затиранием. Устройство 200 также выполнено с возможностью декодирования данных с использованием выбранного режима декодирования для воссоздания блока данных.

Устройство 200 также может быть выполнено с возможностью выбора режима декодирования путем конфигурации для выбора режима декодирования без затирания, если первое количество проекций, proj (p_i=1, q_i=0), равняется количеству k фрагментов данных. Устройство 200 также может быть выполнено с возможностью выбора режима декодирования путем конфигурации для выбора режима декодирования с затиранием, если первое количество проекций, proj (p_i=1, q_i=0), меньше чем количество k фрагментов данных. Устройство также может исследовать то, является ли набор полученных проекций Мохетта, proj (p_i, q_i), достаточным для декодирования блока данных.

Устройство 200 может быть выполнено с возможностью исследования того, является ли набор полученных проекций Мохетта, proj (p_i, q_i), достаточным для декодирования блока данных, путем определения того, является ли полученное первое количество проекций, proj (p_i=1, q_i=0), плюс полученное второе количество проекций, proj(p_i, q_i≠0), равным или больше чем количество строк в блоке данных. Устройство 200 может также запрашивать дополнительные проекции Мохетта proj(p_j,q_j), если полученное первое количество проекций, proj (p_i=1, q_i=0), плюс полученное второе количество проекций, proj(p_i, q_i≠0), меньше чем количество строк в блоке данных, при этом дополнительные проекции Мохетта proj(p_j,q_j) отличаются от первого количества проекций, proj (p_i=1, q_i=0), и второго количества проекций, proj(p_i, q_i≠0).

Устройство 200 также может декодировать блок данных путем использования первого количества проекций, proj (p_i=1, q_i=0), второго количества проекций, proj(p_i, q_i≠0), и необходимых дополнительных проекций Мохетта proj(p_j,q_j). Устройство 200 определяет то, были ли данные корректным образом декодированы путем проверки того, равны ли нулю бинарные элементы декодированных данных.

Фиг. 13a представляет собой схему, на которой изображен возможный вариант реализации устройства 200, в соответствии с иллюстративными аспектами настоящих улучшений. Устройство 200 содержит по меньшей мере один процессор 210 и память 220, при этом память 220 содержит инструкции, которые, при исполнении по меньшей мере одним процессором 210, обуславливают декодирование данных путем использования режима избыточного декодирования по меньшей мере одним процессором 210. Устройство 200 также может содержать схему 230 связи, как описано выше.

Способы, описанные в настоящем документе, могут быть реализованы устройствами 100 и 200, которые основаны на аппаратной схеме, как изображено на фиг. 13b. Аппаратная схема может содержать интегральную схему специального назначения (ASIC), программируемые пользователем вентильные матрицы (ППВМ) или любую другую аппаратную логическую схему, такую как дискретные логические элементы и/или схемы с триггерами, соединенные между собой для выполнения специализированных функций в связи с подходящими регистрами (REG) и/или схемами памяти (MEM). Фиг. 14 представляет собой схематическую диаграмму компьютерной реализации кодирования, в соответствии с иллюстративными аспектами настоящих улучшений. В данном примере по меньшей мере некоторые из этапов, функций, процедур, модулей и/или блоков, описанных в настоящем документе, реализованы в компьютерной программе 125 или 135, которая загружена в память 120 для исполнения схемой обработки, содержащей один или более процессоров 110. Процессор(ы) 110 и память 120 соединены между собой для обеспечения возможности нормального исполнения программы. Устройство 140 ввода/вывода также может быть соединено с процессором(ами) 110 и/или памятью 120 для обеспечения возможности ввода и/или вывода релевантных данных, таких как входной(ые) параметр(ы) и/или результирующий(е) выходной(ые) параметр(ы). Термин «процессор» относится к любой системе или устройству, выполненному с возможностью исполнения программного кода или компьютерных программных инструкций для выполнения конкретной задачи обработки, определения или вычисления. Таким образом, схема обработки, содержащая один или более процессоров 110, выполнена с возможностью осуществления надежно определенных задач обработки, таких как описанные в настоящем документе, при исполнении компьютерной программы 125 или 135. Схема обработки не должна быть специально разработана для исполнения вышеописанных этапов, функций, процедур и/или блоков, а может также выполнять другие задачи.

Например, компьютерная программа 125 или 135 может обуславливать процессор по меньшей мере для:

считывания данных в форме блока данных, отформатированного в соответствии с конкретными настройками так, чтобы он содержал строки и столбцы;

создания, путем применения кодирующего преобразования к полученному блоку данных, набора проекций, proj (p_i, q_i), при этом набор содержит первое количество проекций, proj (p_i=1, q_i=0), и второе количество проекций, proj (p_i, q_i≠0), причем второе количество проекций proj (p_i, q_i≠0) создается путем применения кодирующего преобразования Мохетта к блоку данных,

вывода (S3) созданного набора проекций Мохетта для обеспечения возможности хранения данных в форме проекций Мохетта.

В качестве примера, системная или компьютерная программа 125 или 135 может храниться на компьютерочитаемом носителе информации, в частности, энергонезависимом носителе информации. Компьютерочитаемый носитель информации может содержать одно или более неудаляемых запоминающих устройств, в том числе, но без ограничения, постоянное запоминающее устройство (ПЗУ), оперативное запоминающее устройство (ОЗУ), компакт–диск (CD), цифровой универсальный диск (DVD), Blu–ray диск, память универсальной последовательной шины (USB), жесткий диск (HDD), запоминающее устройство, флеш–память, магнитную ленту или любое другое традиционное запоминающее устройство. Таким образом, компьютерная программа может быть загружена в оперативную память компьютера или эквивалентного устройства обработки для исполнения его схемой обработки.

Фиг. 14 представляет собой схематическую диаграмму, на которой изображен пример компьютерной реализации декодирования, в соответствии с иллюстративными аспектами настоящих улучшений. В данном конкретном примере по меньшей мере некоторые из этапов, функций, процедур, модулей и/или блоков, описанных в настоящем документе, реализованы в компьютерной программе 225 или 235, которая загружена в память 220 для исполнения схемой обработки, содержащей один или более процессоров 210. Процессор(ы) 210 и память 220 соединены между собой для обеспечения возможности нормального исполнения программы. Устройство 240 ввода/вывода также может быть соединено с процессором(ами) 210 и/или памятью 220 для обеспечения возможности ввода и/или вывода релевантных данных, таких как входной(ые) параметр(ы) и/или результирующий(е) выходной(ые) параметр(ы). Термин «процессор» в общем смысле относится к любой системе или устройству, выполненному с возможностью исполнения программного кода или компьютерных программных инструкций для выполнения конкретной задачи обработки, определения или вычисления. Таким образом, схема обработки, содержащая один или более процессоров 210, выполнена с возможностью осуществления надежно определенных задач обработки, таких как описанные в настоящем документе, при исполнении компьютерной программы 225 или 235. Схема обработки не должна быть специально разработана для исполнения вышеописанных этапов, функций, процедур и/или блоков, а может также выполнять другие задачи.

Например, компьютерная программа 225 или 235 может обуславливать процессор по меньшей мере для:

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

считывания закодированных данных, при этом закодированные данные закодированы путем применения кодирующего преобразования Мохетта к блоку данных, отформатированных в соответствии с настройками, при этом закодированные данные содержат набор проекций, proj(p_i, q_i), причем набор содержит первое количество проекций, proj (p_i=1, q_i=0), и второе количество проекций, proj(p_i, q_i≠0);

осуществления проверки того, равно ли первое количество проекций, proj (p_i=1, q_i=0), количеству k фрагментов данных,

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

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

Системная или компьютерная программа 225 или 235 может храниться на компьютерочитаемом носителе информации, в частности, энергонезависимом носителе информации. Компьютерочитаемый носитель информации может содержать одно или более неудаляемых запоминающих устройств, в том числе, но без ограничения, постоянное запоминающее устройство (ПЗУ), оперативное запоминающее устройство (ОЗУ), компакт–диск (CD), цифровой универсальный диск (DVD), Blu–ray диск, память универсальной последовательной шины (USB), жесткий диск (HDD), запоминающее устройство, флеш–память, магнитную ленту или любое другое традиционное запоминающее устройство. Таким образом, компьютерная программа может быть загружена в оперативную память компьютера или эквивалентного устройства обработки для исполнения его схемой обработки.

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

Изобретение относится к средствам для кодирования и декодирования данных. Технический результат заключается в повышении эффективности кодирования. Принимают электронной схемой данные, подлежащие кодированию. Форматируют электронной схемой данные в строки и столбцы. Генерируют электронной схемой первый набор проекций на основе кодирующего преобразования с использованием первого значения параметра для параметра кодирования в кодирующем преобразовании, причем первое значение параметра основано на количестве строк и столбцов упомянутых данных. Генерируют электронной схемой второй набор проекций на основе кодирующего преобразования с использованием второго значения параметра для упомянутого параметра кодирования, которое отличается от первого значения параметра, причем второе значение параметра основано на количестве строк и столбцов упомянутых данных. Сохраняют первый и второй наборы проекций в качестве закодированных данных, соответствующих принятым данным. 5 н. и 13 з.п. ф-лы, 22 ил., 2 табл.

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

прием электронной схемой данных, подлежащих кодированию,

форматирование электронной схемой данных в строки и столбцы,

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

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

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

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

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

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

5. Способ по п. 4, в котором первое значение параметра равняется нулю.

6. Способ по п. 5, в котором второе значение параметра является значением, отличающимся от нуля.

7. Некратковременный компьютерочитаемый носитель информации, хранящий компьютерочитаемые инструкции, которые при исполнении процессором обуславливают выполнение процессором способа по п. 1.

8. Устройство для кодирования, которое выполняет избыточное кодирование данных, содержащее:

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

схему обработки, выполненную с возможностью:

форматирования данных в строки и столбцы,

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

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

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

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

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

считывание электронной схемой закодированных данных,

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

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

декодирование электронной схемой закодированных данных в выбранном одном из первого и второго режимов декодирования и

вывод электронной схемой данных, сгенерированных путем декодирования закодированных данных.

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

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

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

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

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

15. Способ по п. 9, в котором электронная схема содержит множество процессоров, распределенных по сети, при этом каждый процессор исполняет приложение для выполнения по меньшей мере части декодирования.

16. Способ по п. 9, в котором декодирование выполняется процессором с использованием векторизированного кода.

17. Способ по п. 9, в котором декодирование включает использование расширений «одна инструкция, множество данных» (SIMD) для ускорения декодирования закодированных данных.

18. Некратковременный компьютерочитаемый носитель информации, хранящий компьютерочитаемые инструкции, которые при исполнении процессором обуславливают выполнение процессором способа по п. 9.