2025-11-17T17:10:13.329885

Function-Correcting Codes for Locally Bounded Functions

Rajput, Rajan, Freij-Hollanti et al.
In this paper, we introduce a class of functions that assume only a limited number $λ$ of values within a given Hamming $ρ$-ball and call them locally $(ρ, λ)$-bounded functions. We develop function-correcting codes (FCCs) for a subclass of these functions and propose an upper bound on the redundancy of FCCs. The bound is based on the minimum length of an error-correcting code with a given number of codewords and a minimum distance. Furthermore, we provide a sufficient optimality condition for FCCs when $λ= 4$. We also demonstrate that any function can be represented as a locally $(ρ, λ)$-bounded function, illustrating this with a representation of Hamming weight distribution functions. Furthermore, we present another construction of function-correcting codes for Hamming weight distribution functions.
academic

Коды, Исправляющие Функции для Локально Ограниченных Функций

Основная информация

  • ID статьи: 2504.07804
  • Название: Function-Correcting Codes for Locally Bounded Functions
  • Авторы: Charul Rajput, B. Sundar Rajan, Ragnar Freij-Hollanti, Camilla Hollanti
  • Учреждения: Aalto University (Финляндия), Indian Institute of Science (Индия)
  • Классификация: cs.IT, math.IT (Теория информации)
  • Дата публикации: 12 ноября 2025 г. (arXiv v3)
  • Ссылка на статью: https://arxiv.org/abs/2504.07804

Аннотация

В данной работе вводится новый класс функций — локально (ρ, λ)-ограниченные функции, которые принимают не более λ значений в пределах заданного шара Хэмминга радиуса ρ. Авторы разрабатывают коды, исправляющие функции (FCCs), для подклассов этих функций и предлагают верхние границы избыточности на основе минимальной длины кода. В частности, при λ=4 приводятся достаточные условия оптимальности. Статья доказывает, что любая функция может быть представлена как локально (ρ, λ)-ограниченная функция, и иллюстрирует это на примере функции распределения веса Хэмминга, предоставляя альтернативный метод построения FCC для этой функции.

Исследовательский контекст и мотивация

Определение проблемы

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

Значимость исследования

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

Ограничения существующих методов

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

Инновационные аспекты данной работы

Статья обобщает локально двоичные функции до более общей структуры локально (ρ, λ)-ограниченных функций, предоставляя систематические методы построения FCC и теоретический анализ для более широкого класса функций.

Основные вклады

  1. Расширение теоретической базы: Обобщение локально двоичных функций на локально (ρ, λ)-ограниченные функции, предоставляющее более общую систему классификации функций
  2. Верхние границы избыточности:
    • Для локально (2t, 4)-ограниченных функций доказано rf(k,t) ≤ 3t
    • Для общих локально (2t, λ)-ограниченных функций доказано rf(k,t) ≤ N(λ, 2t)
  3. Условия оптимальности: Приводятся достаточные условия для достижения оптимальности FCC при λ=4 (Теорема 5)
  4. Теорема о представлении функций: Доказано, что любая функция может быть представлена как локально (ρ, λ)-ограниченная функция, с конкретным анализом функции распределения веса Хэмминга
  5. Методы построения: Предоставлены систематизированные методы построения FCC на основе отображений раскраски и кодов, исправляющих ошибки
  6. Примеры приложений: Для функции распределения веса Хэмминга приводится лаконичное оптимальное построение

Детальное описание методов

Определение задачи

Код, исправляющий функции (f, t)-FCC: Для функции f: F₂ᵏ → S систематическое кодирование C: F₂ᵏ → F₂ᵏ⁺ʳ называется (f, t)-FCC, если для любых u₁, u₂ ∈ F₂ᵏ, удовлетворяющих f(u₁) ≠ f(u₂), выполняется: d(C(u1),C(u2))≥2t+1d(C(u_1), C(u_2)) \geq 2t+1

где d обозначает расстояние Хэмминга. Это гарантирует правильное восстановление значения функции f(u) даже после t ошибок в битах.

Оптимальная избыточность: rf(k,t) определяется как минимальная избыточность r кодирования C: F₂ᵏ → F₂ᵏ⁺ʳ, для которого существует (f, t)-FCC.

Основные концепции

1. Локально ограниченные функции

Определение (функциональный шар): Функциональный шар функции f: F₂ᵏ → S в точке u ∈ F₂ᵏ радиуса ρ определяется как: Bf(u,ρ)={f(u′)∣u′∈F2k и d(u,u′)≤ρ}B_f(u, \rho) = \{f(u') | u' \in \mathbb{F}_2^k \text{ и } d(u, u') \leq \rho\}

Определение (локально (ρ, λ)-ограниченная функция): Функция f называется локально (ρ, λ)-ограниченной, если для всех u ∈ F₂ᵏ выполняется |Bf(u, ρ)| ≤ λ.

Условие непрерывности: Предполагается существование полного порядка ≺ на Im(f), такого что каждый Bf(u, ρ) образует непрерывный блок (contiguous block).

2. Отображение раскраски (Coloring Mapping)

Ключевая идея Леммы 1: Для локально (ρ, λ)-ограниченных функций, удовлетворяющих условию непрерывности, существует отображение Colf: F₂ᵏ → λ, такое что для любых d(u,v) ≤ ρ и f(u) ≠ f(v) выполняется Colf(u) ≠ Colf(v).

Метод построения:

  • Пусть Im(f) = {y₀ ≺ y₁ ≺ ... ≺ yₑ₋₁}
  • Определим γ: Im(f) → λ, γ(yⱼ) = 1 + (j mod λ) (циклическая раскраска)
  • Определим Colf(u) = γ(f(u))

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

Методы построения FCC

Построение 1: Случай λ=4 (Лемма 2)

Функция кодирования: Enc(u) = (u, uₚ), где uₚ = (u'ₚ)ᵗ, и

000 & \text{если } Col_f(u) = 1\\ 110 & \text{если } Col_f(u) = 2\\ 101 & \text{если } Col_f(u) = 3\\ 011 & \text{если } Col_f(u) = 4 \end{cases}$$ **Доказательство корректности**: - **Случай 1**: При d(u,v) ≥ 2t+1 непосредственно выполняется d(Enc(u), Enc(v)) ≥ 2t+1 - **Случай 2**: При d(u,v) ≤ 2t из свойства Colf следует Colf(u) ≠ Colf(v), поэтому d(u'ₚ, v'ₚ) = 2, откуда d(uₚ, vₚ) = 2t, и с учётом d(u,v) ≥ 1 получаем общее расстояние ≥2t+1 **Избыточность**: rf(k,t) ≤ 3t #### Построение 2: Общий случай λ (Теорема 6) **Функция кодирования**: Используется двоичный код, исправляющий ошибки C, с λ кодовыми словами, минимальным расстоянием 2t и длиной N(λ, 2t). Пусть кодовые слова — C₁, C₂, ..., Cλ, определим: $$Enc(u) = (u, u_p), \quad u_p = C_{Col_f(u)}$$ **Верхняя граница избыточности**: rf(k,t) ≤ N(λ, 2t) **Ключевые технические моменты**: - Использование отображения раскраски для преобразования значений функции в конечное множество [λ] - Применение ECC для гарантирования достаточного расстояния между битами избыточности, соответствующими разным цветам - Умелое объединение расстояния информационных битов и расстояния битов избыточности #### Построение 3: Функция распределения веса Хэмминга (Теорема 8) Для ∆ₜ(u) = ⌊wt(u)/T⌋, когда (4t)/(m-1) ≥ T > (4t)/m: **Функция кодирования**: Пусть a = ⌈m/2⌉ + 1, используется ECC C с a кодовыми словами и минимальным расстоянием 2t, определим: $$Enc(u) = (u, u_p), \quad u_p = C_{\Delta_T(u) \mod a}$$ **Верхняя граница избыточности**: r∆ₜ(k,t) ≤ N(⌈m/2⌉ + 1, 2t) В частности, при t ≥ T > 2t/3 имеем r∆ₜ(k,t) ≤ 3t. ### Технические инновации 1. **Единая база**: Через локальную ограниченность и условие непрерывности объединяются различные классы функций в одну базу 2. **Техника раскраски**: Инновационное использование циклической раскраски преобразует проблему отображения значений функции в задачу комбинаторной раскраски 3. **Модульное проектирование**: Построение FCC разлагается на два независимых модуля — отображение раскраски и ECC, повышая гибкость 4. **Сочетание теории и построения**: Не только приводятся верхние границы, но и предоставляются явные построения, достигающие этих границ 5. **Оптимизация параметров**: Для различных диапазонов параметров приводится тонкий анализ границ ## Экспериментальная установка Данная работа является чисто теоретической и не включает традиционные эксперименты. Основная верификация методов проводится через математические доказательства и теоретический анализ. ### Методы теоретической верификации 1. **Конструктивные доказательства**: Через явное построение функций кодирования, удовлетворяющих условиям, доказывается достижимость верхних границ избыточности 2. **Анализ нижних границ**: Использование границы Плоткина и теории матриц требований расстояния для установления нижних границ избыточности 3. **Верификация оптимальности**: Через совпадение верхних и нижних границ доказывается оптимальность построений при определённых параметрах ### Анализ примеров #### Примеры 1-3: Матрицы требований расстояния Через конкретные функции f: F₂² → {0,1} демонстрируется процесс вычисления DRM и FDM, верифицируя операциональность теоретической базы. #### Пример 4: Функция переупорядочивания в лексикографическом порядке Демонстрируется конкретная функция, удовлетворяющая условию непрерывности: $$f(u) = 0^{k-wt(u)}1^{wt(u)}$$ Доказывается, что функциональный шар Bf(u, ρ) = {0ᵏ⁻ʲ1ʲ : j ∈ Wu,ρ} образует непрерывный блок. ## Результаты экспериментов ### Основные теоретические результаты #### 1. Верхние границы избыточности (основной результат) **Теорема 6**: Для локально (2t, λ)-ограниченных функций, $$r_f(k,t) \leq N(\lambda, 2t)$$ **Лемма 3**: N(4, 2t) = 3t (точное значение) **Следствие**: Для локально (2t, 4)-ограниченных функций rf(k,t) ≤ 3t #### 2. Условия оптимальности **Теорема 5**: Для локально (2t, 4)-ограниченной функции, если |Im(f)| ≥ 3 и существуют u₁, u₂, u₃, удовлетворяющие: - f(ui) ≠ f(uj) (i ≠ j) - d(u₁, u₂) = 1, d(u₃, u₁) = 1, d(u₃, u₂) = 2 то rf(k,t) = 3t является оптимальным. **Схема доказательства**: Через границу Плоткина получается нижняя граница rf(k,t) ≥ 3t, объединение с верхней границей даёт плотность. #### 3. Функция распределения веса Хэмминга **Теорема 7**: ∆ₜ является локально (2t, ⌊4t/T⌋ + 2)-ограниченной функцией **Следствия**: - T > 4t: ∆ₜ является 2t-локально двоичной функцией - 4t ≥ T > 2t: ∆ₜ является локально (2t, 3)-ограниченной функцией - t ≥ T > 2t/3: r∆ₜ(k,t) ≤ 3t **Следствие 2**: Функция веса Хэмминга является локально (2t, 4t+2)-ограниченной функцией ### Сравнение границ | Тип функции | λ значение | Верхняя граница избыточности | Оптимальность | |---------|-----|-----------|--------| | 2t-локально двоичная | 2 | 2t | Оптимальна [1] | | Локально (2t,3) | 3 | N(3,2t) | - | | Локально (2t,4) | 4 | 3t | Условно оптимальна | | Общая локально (2t,λ) | λ | N(λ,2t) | - | ### Теоретические открытия 1. **Универсальность**: Любая функция f: F₂ᵏ → S может быть представлена как локально (ρ, λ)-ограниченная функция, где λ = max_{u∈F₂ᵏ} |Bf(u, ρ)| 2. **Соотношение параметров**: Для функции распределения веса Хэмминга λ обратно пропорциональна пороговому значению T: чем больше T, тем меньше λ, тем выше эффективность кодирования 3. **Соотношение длин кодов**: Точный результат N(4, 2t) = 3t обеспечивает теоретическую гарантию для случая λ=4 4. **Важность непрерывности**: Условие непрерывности является ключевым предположением для методов построения, гарантируя эффективность отображения раскраски ## Связанные работы ### Основная теория FCC **Ленц и др. [1] (2023)**: Первое систематическое представление теории FCC - Определены матрица требований расстояния (DRM) и матрица функционального расстояния (FDM) - Предоставлены построения для локально двоичных функций, функций веса Хэмминга - Установлены базовые верхние и нижние границы ### Расширения и приложения **Xia и др. [12] (2024)**: Расширение на канал чтения символьных пар - Предложены коды FCC для символьных пар (FCSPCs) - Оптимизация для специфических моделей каналов **Premlal & Rajan [13] (2025)**: Исследование нижних границ избыточности - Предоставлены общие нижние границы избыточности FCC - Доказана плотность для линейных функций **Ge и др. [14] (2025)**: Оптимизация функции веса Хэмминга - Улучшены границы избыточности для функции веса Хэмминга - Предоставлены оптимальные построения, достигающие нижних границ **Singh и др. [15] (2025)**: Канал чтения b-символов - Расширение на b-символьный канал чтения над конечными полями - Введены нерегулярные коды b-символьного расстояния ### Преимущества данной работы 1. **Теоретическая универсальность**: Предоставляет единую базу локально ограниченных функций, охватывающую более широкий класс функций 2. **Систематичность построений**: Методы построения на основе отображения раскраски обладают модульностью и расширяемостью 3. **Тонкая параметризация**: Для различных значений λ приводятся точные границы избыточности 4. **Гибкость приложений**: Доказано, что любая функция может быть включена в эту базу, повышая применимость теории ## Заключение и обсуждение ### Основные выводы 1. **Теоретическая база**: Успешно установлена система теории локально (ρ, λ)-ограниченных функций, обобщающая концепцию локально двоичных функций 2. **Границы избыточности**: Для локально (2t, λ)-ограниченных функций, удовлетворяющих условию непрерывности, доказано rf(k,t) ≤ N(λ, 2t), в частности при λ=4 rf(k,t) ≤ 3t 3. **Оптимальность**: Приведены достаточные условия для достижения оптимальности при λ=4, доказано N(4, 2t) = 3t 4. **Универсальность**: Доказано, что любая функция может быть представлена как локально (ρ, λ)-ограниченная функция, расширяя применимость FCC 5. **Примеры приложений**: Для функции распределения веса Хэмминга предоставлено лаконичное оптимальное построение ### Ограничения 1. **Предположение о непрерывности**: Все построения зависят от предположения, что функциональные шары образуют непрерывные блоки, ограничивая область применения - Не все локально ограниченные функции удовлетворяют этому условию - Для функций, не удовлетворяющих непрерывности, методы неприменимы 2. **Ограничение на двоичное поле**: Текущая теория применима только к F₂ᵏ, расширение на общие конечные поля Fqᵏ ещё не завершено 3. **Условия оптимальности**: Приведены только достаточные условия для λ=4, характеризация оптимальности для других значений λ неполна 4. **Зависимость от ECC**: Верхние границы избыточности зависят от существования N(λ, 2t), а построение оптимальных ECC само по себе является сложной задачей 5. **Верификация практичности**: Отсутствует оценка производительности и анализ сложности в реальных сценариях приложений ### Направления будущих исследований 1. **Расширение на конечные поля**: Обобщение теории на общие конечные поля Fqᵏ (авторы упоминают, что это в процессе) 2. **Ослабление условия непрерывности**: Исследование построений FCC для локально ограниченных функций, не удовлетворяющих условию непрерывности 3. **Полная характеризация оптимальности**: Приведение необходимых и достаточных условий оптимальности для общих значений λ 4. **Вычислительная сложность**: Анализ временной сложности алгоритмов кодирования и декодирования 5. **Практические приложения**: Верификация эффективности методов в реальных сценариях (хранение данных, машинное обучение) 6. **Несистематические коды**: Исследование, могут ли несистематические FCC дополнительно снизить избыточность ## Глубокая оценка ### Преимущества #### 1. Теоретическая инновативность (★★★★★) - **Обобщение концепций**: Обобщение от локально двоичных функций к локально (ρ, λ)-ограниченным функциям естественно и значимо - **Единая база**: Предоставляет единый взгляд на обработку различных классов функций - **Новая техника**: Метод отображения раскраски умело преобразует проблему защиты функций в комбинаторную задачу #### 2. Математическая строгость (★★★★★) - Все теоремы имеют полные и строгие доказательства - Логическая цепь ясна, от базовых концепций к основным результатам - Используются различные инструменты комбинаторики и теории кодирования #### 3. Полнота результатов (★★★★☆) - Приводятся верхние границы и условия оптимальности - Предоставляются явные методы построения - Теория верифицируется на конкретных классах функций - Отсутствует систематическое исследование нижних границ (в основном опирается на существующие результаты) #### 4. Ясность изложения (★★★★★) - Структура ясна, от предварительных знаний к основным результатам логично организована - Конкретные примеры помогают понять абстрактные концепции - Система обозначений согласована, определения чёткие ### Недостатки #### 1. Ограничение области применения **Предположение о непрерывности**: Лемма 1 и все последующие построения зависят от предположения, что функциональные шары образуют непрерывные блоки. Хотя Пример 4 демонстрирует функции, удовлетворяющие этому условию: - Отсутствует систематическая характеризация функций, удовлетворяющих условию - Нет альтернативных методов для функций, не удовлетворяющих условию - Сложность проверки непрерывности не обсуждается #### 2. Полнота теории - **Условия оптимальности**: Теорема 5 приводит только достаточные условия для λ=4, аналогичные результаты для λ>4 отсутствуют - **Исследование нижних границ**: В основном используются существующие границы Плоткина, специализированные нижние границы для локально ограниченных функций отсутствуют - **Оптимизация параметров**: Точные значения N(λ, 2t) приводятся только для λ=4, в других случаях зависит от теории ECC #### 3. Оценка практичности - **Вычислительная сложность**: Не анализируется временная сложность кодирования и декодирования - **Практические приложения**: Отсутствует оценка производительности в конкретных сценариях (хранение данных, машинное обучение) - **Сравнение с ECC**: Хотя Замечание 1 указывает на преимущество FCC над ECC, отсутствует количественное сравнение #### 4. Технические детали - **Отображение раскраски**: Является ли циклическая раскраска оптимальной? Существуют ли альтернативные схемы раскраски? - **Выбор ECC**: Как выбрать подходящий ECC для минимизации N(λ, 2t)? - **Зависимость параметров**: Зависимость избыточности от k (длины информации) не уточняется ### Влияние на область #### Вклад в область (★★★★☆) 1. **Теоретическое расширение**: Предоставляет важное обобщение теории FCC, заполняя пробел между локально двоичными функциями и общими функциями 2. **Методология**: Метод отображения раскраски предоставляет новый инструмент для последующих исследований 3. **Потенциал приложений**: Доказано, что любая функция может быть представлена как локально ограниченная, расширяя применимость FCC #### Практическая ценность (★★★☆☆) - **Теоретическая ориентация**: В настоящее время в основном теоретический вклад, практические приложения требуют дальнейшей работы - **Осуществимость построений**: Предоставленные методы построения могут быть непосредственно реализованы, имеют практическую основу - **Гибкость параметров**: Различные значения λ соответствуют разным сценариям приложений, предоставляя гибкость проектирования #### Воспроизводимость (★★★★★) - Все построения имеют явные алгоритмы - Доказательства полны, могут быть независимо верифицированы - Примеры конкретны, облегчают понимание и реализацию ### Применимые сценарии #### 1. Идеальные сценарии - **Характеристики функции**: Функциональные шары образуют непрерывные блоки (например, функция распределения веса Хэмминга) - **Диапазон параметров**: λ относительно мало (например, λ≤4), можно получить плотные границы - **Требования приложений**: Требуется защита только значения функции, а не полного сообщения #### 2. Конкретные приложения - **Хранение данных**: Защита метаданных архивных данных (например, размер файла, контрольная сумма) - **Машинное обучение**: Защита выходных данных классификации, уровня уверенности - **Распределённые вычисления**: Защита значений функций промежуточных результатов вычисления - **Интернет вещей**: Защита статистических характеристик данных датчиков #### 3. Неприменимые сценарии - Функциональные шары не образуют непрерывные блоки - Требуется защита полного сообщения (в этом случае ECC более подходящий) - λ очень велико (близко к |Im(f)|), преимущество FCC неочевидно ## Ключевые ссылки [1] A. Lenz, R. Bitar, A. Wachter-Zeh, and E. Yaakobi, "Function-correcting codes," IEEE Trans. Inf. Theory, 2023. - **Пионерская работа по FCC**, устанавливает базовую теоретическую базу [13] R. Premlal and B. S. Rajan, "On function-correcting codes," IEEE Trans. Inf. Theory, 2025. - **Исследование нижних границ избыточности**, предоставляет теоретическую основу для данной работы [14] G. Ge, Z. Xu, X. Zhang, and Y. Zhang, "Optimal redundancy of function-correcting codes," arXiv preprint, 2025. - **Оптимальное построение для функции веса Хэмминга**, сравнимо с построениями в данной работе [17] M. Plotkin, "Binary codes with specified minimum distance," IRE Trans. Inf. Theory, 1960. - **Граница Плоткина**, используется для доказательства нижних границ --- ## Общая оценка - **Теоретическая инновативность**: ★★★★★ - **Техническая глубина**: ★★★★☆ - **Практическая ценность**: ★★★☆☆ - **Качество изложения**: ★★★★★ - **Комплексная оценка**: ★★★★☆ Это высококачественная теоретическая работа, вносящая значительный вклад в область FCC. Предложение концепции локально ограниченных функций и применение метода отображения раскраски оба обладают инновационностью. Хотя в верификации практичности и полноте теории есть место для улучшения, как фундаментальное теоретическое исследование, данная работа создаёт прочную основу для последующих работ. Особенно рекомендуется исследователям, интересующимся теорией кодирования и теорией информации.