Look-Up Table¶

Look-Up Table (LUT, таблица поиска, таблица соответствия) — это структура данных, используемая в вычислительной технике, электронике и цифровой обработке сигналов для замены сложных вычислений простым поиском заранее рассчитанных значений. Вместо выполнения ресурсоёмких операций в реальном времени система обращается к предварительно сохранённой таблице, что значительно ускоряет обработку данных. LUT представляет собой массив или ассоциативный список, где каждому входному значению (индексу или ключу) ставится в соответствие одно или несколько выходных значений.

¶Принцип работы

Основная идея LUT заключается в том, что результат вычисления для некоторого набора входных данных определяется не путём выполнения алгоритма, а прямым обращением к памяти по адресу, соответствующему входному значению. Если входной сигнал представлен конечным числом дискретных состояний (например, 8-битное число от 0 до 255), то для каждого возможного значения можно заранее рассчитать и сохранить результат. При поступлении входного сигнала система считывает ячейку памяти с соответствующим адресом и выводит сохранённое значение.

В цифровой электронике LUT часто реализуется на программируемых логических интегральных схемах (ПЛИС, FPGA). В таких схемах LUT является базовым логическим элементом, способным реализовать любую булеву функцию от нескольких переменных (обычно от 4 до 6). Входные переменные используются как адресные биты, а выходное значение хранится в ячейке памяти, инициализированной при конфигурации ПЛИС.

¶История

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

В 1950-х годах, с развитием цифровой обработки сигналов, LUT стали применяться в аппаратных реализациях фильтров и преобразований. В 1960-х годах, с появлением интегральных схем, LUT начали использоваться в микропроцессорах для ускорения операций с плавающей запятой. Современные ПЛИС, появившиеся в 1980-х годах, сделали LUT основным строительным блоком цифровой логики.

¶Классификация LUT

¶По способу хранения данных

• Одномерные LUT — простейший вид, где входное значение является целочисленным индексом, а выходное — заранее рассчитанным числом. Пример: таблица синусов для углов от 0 до 359 градусов.
• Многомерные LUT — таблицы с несколькими входными переменными, где выходное значение зависит от комбинации значений. В цифровой электронике это реализуется как LUT с несколькими адресными входами.
• Ассоциативные LUT — таблицы, где поиск осуществляется не по индексу, а по ключу (например, хеш-таблицы). Используются в программных реализациях для сопоставления произвольных данных.

¶По области применения

• Аппаратные LUT — реализованные в виде цифровых схем (в ПЛИС, ASIC, процессорах). Обеспечивают максимальную скорость, но фиксированы по размеру.
• Программные LUT — реализованные в виде массивов данных в оперативной памяти. Более гибкие, но уступают аппаратным по скорости доступа.

¶Устройство и характеристики

¶В цифровой электронике

В ПЛИС LUT обычно состоит из набора ячеек статической памяти (SRAM), каждая из которых хранит один бит выходного значения. Количество входных переменных определяет число адресных битов, а значит, и размер таблицы. Например, 4-входовая LUT имеет 2^4 = 16 ячеек памяти, каждая из которых хранит один бит. Для реализации более сложных функций несколько LUT могут объединяться в цепочки.

Характеристики аппаратных LUT:

• Количество входов — обычно от 4 до 6, реже до 8.
• Время доступа — единицы наносекунд (в современных ПЛИС).
• Энергопотребление — зависит от технологии изготовления и частоты переключений.

¶В программной реализации

Программные LUT представляют собой массивы (списки, словари) в памяти. Размер таблицы определяется количеством возможных входных значений. Для 8-битного входного числа (256 значений) таблица занимает 256 ячеек; для 16-битного (65536 значений) — 65536 ячеек. Время доступа к элементу массива составляет единицы наносекунд в оперативной памяти.

¶Применение

¶Цифровая обработка сигналов (ЦОС)

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

¶Графика и видео

В компьютерной графике LUT используются для коррекции цвета (color grading), гамма-коррекции, преобразования цветовых пространств (RGB в YUV). В видеокартах LUT применяются для применения цветовых фильтров и эффектов. Профессиональные мониторы и калибраторы используют 3D LUT для точной цветопередачи.

¶Криптография

В алгоритмах шифрования (например, AES) LUT применяются для реализации S-блоков (substitution boxes) — таблиц замены, которые отображают входные байты на выходные. Это позволяет выполнять нелинейные преобразования с высокой скоростью.

¶Нейронные сети

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

¶ПЛИС и проектирование цифровых схем

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

¶Программирование

В программировании LUT используются для оптимизации кода: например, для быстрого вычисления количества битов в числе (popcount), для проверки чётности, для преобразования кодировок. В компиляторах LUT применяются для оптимизации таблиц переходов (switch-case).

¶Преимущества и недостатки

¶Преимущества

• Высокая скорость — обращение к памяти занимает фиксированное время, независимо от сложности вычисления.
• Простота реализации — LUT не требует сложных вычислительных блоков.
• Предсказуемость — время выполнения не зависит от входных данных (отсутствие ветвлений).

¶Недостатки

• Ограниченный размер — для больших входных диапазонов (например, 32-битные числа) таблица становится непрактично большой (4 гигабайта для 32-битного входа).
• Фиксированная точность — значения в таблице имеют ограниченную разрядность, что может приводить к ошибкам округления.
• Необходимость предварительного расчёта — таблицу нужно заполнить заранее, что требует времени и памяти.
• Отсутствие гибкости — для изменения функции требуется пересчёт и загрузка новой таблицы.

¶Примеры

¶Пример 1: Таблица синусов

Для 8-битного входного угла (0–255, соответствующих 0–360 градусам) LUT может содержать 256 значений синуса, каждое представленное 8-битным числом. Размер таблицы — 256 байт. Обращение к таблице позволяет получить значение синуса за один такт.

¶Пример 2: Гамма-коррекция

В графике LUT для гамма-коррекции содержит 256 входных значений яркости (0–255) и 256 выходных значений, рассчитанных по формуле output = 255 * (input/255)^(1/gamma). Такая таблица позволяет быстро применять гамма-коррекцию к изображению.

¶Пример 3: S-блок AES

В алгоритме AES используется S-блок, который представляет собой 256-байтную LUT, отображающую каждый байт на другой байт в соответствии с мультипликативным обратным в поле Галуа. Эта таблица реализует нелинейное преобразование, необходимое для шифрования.

¶Интересные факты

• В первых ПЛИС (например, Xilinx XC2000) LUT имели всего 3 входа. Современные ПЛИС (Xilinx 7-series, Intel Stratix 10) используют 6-входовые LUT.
• В некоторых процессорах (например, в ARM Cortex-M) LUT используются для ускорения вычисления тригонометрических функций в библиотеке math.h.
• В компьютерной графике 3D LUT (трёхмерные таблицы) позволяют выполнять сложные цветовые преобразования, например, имитацию плёнки или стилистическую обработку.
• В криптографии LUT могут быть атакованы с помощью кэш-тайминга, когда злоумышленник измеряет время доступа к памяти и восстанавливает ключ.

¶Источники

• Хоровиц П., Хилл У. «Искусство схемотехники». — М.: Мир, 2003.
• Уэйкерли Дж. «Цифровые устройства и микропроцессорные системы». — М.: Постмаркет, 2000.
• Спецификация ПЛИС Xilinx 7 Series (UG479).
• Стандарт AES (FIPS PUB 197).
• Документация по библиотеке math.h (ARM CMSIS-DSP).