Вычислительное устройство, хранящее таблицы соответствия для вычисления функции

Вычислительное устройство, хранящее таблицы соответствия для вычисления функции

Иллюстрации

Показать все

Реферат

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

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

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

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

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

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

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

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

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

Защита против этого сценария атаки показала себя очень трудной. Одним типом контрмеры является так называемая криптография "белый ящик". При криптографии "белый ящик" ключ и алгоритм комбинируются. Получившийся алгоритм работает только для одного конкретного ключа. Далее алгоритм может осуществляться в виде так называемой сети таблиц соответствия. Вычисления преобразуются в последовательность соответствий в зависимых от ключа таблицах. См., например, работу "White-Box Cryptography and an AES Implementation" ("Криптография "белый ящик" и осуществление AES") авторства S. Chow, P. Eisen, H. Johnson, P.C. van Oorschot для примера этого подхода.

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

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

Патент США 7996671 предлагает увеличение сопротивления компьютерных программ против атак по сторонним каналам путем улучшенной компиляции. Поскольку атаки с анализом мощности полагаются на измеренный расход мощности, сопротивление увеличивается путем компилирования с целью уменьшения расхода мощности. Компилятор прогнозирует компиляцию, которая является наиболее энергосберегающей, и выбирает ее. Наблюдается, что уменьшение потребления энергии увеличивает шум/вариацию мощности и улучшает сопротивление сторонних каналов.

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

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

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

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

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

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

Использование закодированных входных значений вместо самих входных значений способствует обфускации программы, т.е. увеличивается сложность обратного проектирования программы. Сохраненные таблицы соответствия имеют свойства исправления ошибок. Эти свойства могут быть задействованы двумя способами. Все закодированные входные значения, которые различаются не более чем на число бит, равное способности к исправлению ошибок (также называемой "t"), от одного и того же кодового слова, обрабатываются одним и тем же образом таблицей соответствия. Таким образом, атака с неисправностями, вызывающая не более "t" битовых ошибок, не вызовет ошибку, относящуюся к безопасности, например ошибку корреляции с ключом. Атаки с неисправностями становятся все более сложными с каждой дополнительной ошибкой, которая должна быть внесена. Путем выполнения вычислений с использованием таблиц исправления ошибок атаки с неисправностями становится труднее выполнить. С другой стороны, таблица соответствия не обязана выдавать один и тот же результат для двух входных данных, которые принадлежат к одному и тому же входному значению, т.е. близки к одному и тому же кодовому слову. Поскольку таблица соответствия устойчива против ошибок, эти ошибки могут также быть добавлены специально. Обратное проектирование сильнее усложняется, когда распределяется фиксированное взаимоотношение между значениями и кодированием. Когда используются таблицы исправления ошибок, одно входное значение может быть представлено множеством закодированных значений. В частности, автоматизированное обратное проектирование, которое зависит от нахождения корреляций между входными значениями, выходными значениями и внутренними переменными, будет требовать данные от существенно большего количества запусков для преодоления этого статистического препятствия. Два способа, которыми таблицы исправления ошибок противостоят атакам с неисправностями и с обратным проектированием, должны исключать друг друга, оба могут быть использованы одновременно.

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

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

Однако, это не необходимо: в одном варианте осуществления первый код исправления ошибок таблицы соответствия тот же самый, что и второй код исправления ошибок этой таблицы соответствия. В одном варианте осуществления все первые коды исправления ошибок таблиц соответствия одни и те же и те же самые, что и все вторые коды исправления ошибок таблиц соответствия.

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

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

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

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

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

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

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

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

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

Например, если Y обозначает незакодированную область, т.е. простые (входные) значения. И X обозначает пространство кодовых слов. Пусть M - вложение области Y в большую область X, и пусть M^-1 - преобразование из области X в Y, где малая ошибка e в значении M(v) из X все так же преобразуется обратно в v. Кодирование входного значения y может быть выполнено посредством вычисления M(y). Последнее может быть выполнено путем применения функции кодирования, например линейного матричного умножения, и т.п., но также посредством таблицы соответствия. Пусть g - функция из Y в Y, которая осуществляет обфускацию. Применение g скрывает значение переменных. Это может комбинироваться с кодированием, данным выше, следующим образом: y преобразуется в M(g(y)). Например, g может быть выбрано случайным образом, по меньшей мере g не является тождеством.

Использование осуществления функции на основе таблиц, например, полученной специальным компилятором или выполненной вручную, приведет к большему занимаемому месту. Кроме того, поскольку кодирование увеличивает размер значений, таблицы больше, чем без кодирования исправления ошибок. Для многих приложений преимущества перевешивают это увеличение в объеме. Некоторые интересные коды, которые можно использовать, для первого и/или второго кода исправления ошибок, следующие: [7, 4, 3], [11, 4, 5], [12, 8, 3], [16, 8, 5], [21, 16, 3]. Эти коды комбинируют относительно низкое значение "t", т.е. 1 или 2, с размером незакодированных блоков, который хорошо соотносится с двоичными архитектурами. Однако нет причин ограничивать незакодированный входной битовый размер (k) степенями 2, хотя это удобно. В последнем случае можно использовать такие коды, как [9, 5, 3], [13, 5, 5], [10, 6, 3], [14, 6, 5] и т.д.

Использования кодов, имеющих равное минимальное расстояние, возможно, хотя нечетное минимальное расстояние предпочтительно. Это означает, что такие коды, как [8, 4, 4], [10, 4, 4], также могут быть использованы.

Использование равного минимального расстояния (d) может быть важно для обнаружения неисправностей. При d=2t можно исправить (t-1) ошибок и обнаружить вплоть до t битовых ошибок. Например, может быть добавлена логика ошибок, которая проверяет, присутствует ли t ошибок. Также, при использовании несовершенного кода логика ошибок может обнаруживать неисправимые битовые комбинации. Когда такая проблема обнаруживается, могут быть предприняты надлежащие действия, например отмена процесса, выдача ошибки и т.д.

Хотя линейные коды должны быть предпочтительны, поскольку они существенно упростят проектирование компилятора, линейная структура не приводит к улучшенной таблице соответствия. Это означает, что нелинейные коды также могут быть использованы, такие как [14, 7, 5], [15, 7, 6], [15, 8, 5] и [16, 8, 6].

Однако для сохранения малого размера таблиц предпочтительно сохранять n малым, например 12 или ниже, или даже ниже 11; и сохранять размерность малой, например 8 или меньше, возможно 4.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

фиг.1 изображает схему, иллюстрирующую таблицу соответствия исправления ошибок,

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

фиг.3 изображает структурную схему, иллюстрирующую сеть таблиц соответствия,

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

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

фиг.5b изображает примерные значения, соответствующие фиг.5a,

фиг.6 изображает блок-схему, иллюстрирующую компиляцию,

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

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

Подробное описание вариантов осуществления

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

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

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

Таблица 100 соответствия имеет особое свойство в отношении кода исправления ошибок C. Код C содержит 2^k кодовых слов из n бит. Любые два кодовых слова в C отличаются не менее, чем на d бит. Параметры кода называются кодом [n,k,d]. Число t=floor((d-1)/2) обозначает число битовых ошибок, которые могут быть исправлены. То есть, если инвертируется не больше, чем t бит в кодовом слове, то существует уникальное кодовое слово, которое является наиближайшим к получающейся в результате битовой строке. Число k называется размерностью кода, число d называется минимальным расстоянием. Использование размерности слова не подразумевает, что линейный код необходим, хотя это предпочтительно. Мы будем использовать размерность слова для указания, что код содержит по меньшей мере 2 в степени размерности кодовых слов.

Число t называется способностью к исправлению ошибок кода. Если необходимо указать, что первый код исправления ошибок может отличаться от второго кода исправления ошибок, добавляется индекс, чтобы, таким образом, делалась ссылка на n1, k1, t1 и на n2, k2, t2. Однако в большинств