Códigos Correctores de Funciones para Funciones Localmente Acotadas

Información Básica

• ID del Artículo: 2504.07804
• Título: Function-Correcting Codes for Locally Bounded Functions
• Autores: Charul Rajput, B. Sundar Rajan, Ragnar Freij-Hollanti, Camilla Hollanti
• Instituciones: Universidad Aalto (Finlandia), Instituto Indio de Ciencias (India)
• Clasificación: cs.IT, math.IT (Teoría de la Información)
• Fecha de Publicación: 12 de noviembre de 2025 (arXiv v3)
• Enlace del Artículo: https://arxiv.org/abs/2504.07804

Resumen

Este artículo introduce una nueva clase de funciones denominadas funciones localmente (ρ, λ)-acotadas, que toman únicamente λ valores finitos dentro de una bola de Hamming ρ dada. Los autores desarrollan códigos correctores de funciones (FCCs) para subclases de estas funciones y proponen cotas superiores de redundancia basadas en la longitud mínima del código. En particular, cuando λ=4, se proporcionan condiciones de optimalidad suficientes. El artículo también demuestra que cualquier función puede representarse como una función localmente (ρ, λ)-acotada e ilustra esto con funciones de distribución de peso de Hamming, proporcionando además un método alternativo de construcción de FCC para esta función.

Antecedentes y Motivación de la Investigación

Definición del Problema

En procesos de transmisión y almacenamiento de datos, los códigos correctores de errores (ECCs) tradicionales se esfuerzan por proteger vectores de mensajes completos contra errores. Sin embargo, en muchos escenarios prácticos, el receptor solo se interesa en un atributo específico o valor de función del mensaje (como salidas de aprendizaje automático, peso de Hamming, etc.), no en el mensaje completo. Los códigos correctores de funciones (FCCs) están diseñados precisamente para resolver este problema.

Importancia de la Investigación

1. Mejora de Eficiencia: Cuando el mensaje es grande pero la salida de la función es pequeña, proteger el valor de la función es más eficiente que proteger el mensaje completo
2. Aplicaciones Prácticas: Posee valor importante en escenarios como almacenamiento de datos de archivo, protección de salidas de algoritmos de aprendizaje automático, resiliencia consciente del contexto
3. Significado Teórico: Los FCCs proporcionan una nueva perspectiva de investigación para la teoría de la información, conectando la teoría de codificación y la protección de funciones

Limitaciones de Métodos Existentes

• Lenz et al. 1 propusieron por primera vez la teoría de FCCs, diseñando códigos para familias de funciones específicas como funciones localmente binarias y funciones de peso de Hamming
• El trabajo existente se concentra principalmente en categorías de funciones específicas, careciendo de un marco teórico unificado
• La investigación sobre límites de redundancia para funciones generales es insuficiente
• La caracterización de condiciones de optimalidad no es lo suficientemente completa

Puntos Innovadores de Este Artículo

Este artículo generaliza funciones localmente binarias al marco más general de funciones localmente (ρ, λ)-acotadas, proporcionando métodos de construcción de FCC sistemáticos y análisis teóricos para una clase más amplia de funciones.

Contribuciones Principales

1. Extensión del Marco Teórico: Generaliza funciones localmente binarias a funciones localmente (ρ, λ)-acotadas, proporcionando un sistema de clasificación de funciones más general
2. Cotas Superiores de Redundancia:
   • Para funciones localmente (2t, 4)-acotadas, se demuestra que rf(k,t) ≤ 3t
   • Para funciones localmente (2t, λ)-acotadas generales, se demuestra que rf(k,t) ≤ N(λ, 2t)
3. Condiciones de Optimalidad: Se proporcionan condiciones suficientes para que los FCCs alcancen la optimalidad cuando λ=4 (Teorema 5)
4. Teorema de Representación de Funciones: Se demuestra que cualquier función puede representarse como una función localmente (ρ, λ)-acotada, con análisis específico de funciones de distribución de peso de Hamming
5. Métodos de Construcción: Se proporcionan métodos de construcción de FCC sistematizados basados en mapeos de coloración y códigos correctores de errores
6. Instancias de Aplicación: Se proporciona una construcción óptima concisa para funciones de distribución de peso de Hamming

Explicación Detallada de Métodos

Definición de Tareas

Código Corrector de Funciones (f, t)-FCC: Dada una función f: F₂ᵏ → S, una codificación sistemática C: F₂ᵏ → F₂ᵏ⁺ʳ se denomina (f, t)-FCC si para cualesquiera u₁, u₂ ∈ F₂ᵏ que satisfacen f(u₁) ≠ f(u₂), se cumple: $d(C(u_1), C(u_2)) \geq 2t+1$

donde d denota la distancia de Hamming. Esto asegura que el valor de función f(u) pueda recuperarse correctamente después de t errores de bits.

Redundancia Óptima: rf(k,t) se define como la redundancia mínima r de una codificación C: F₂ᵏ → F₂ᵏ⁺ʳ cuando existe un (f, t)-FCC.

Conceptos Principales

1. Funciones Localmente Acotadas

Definición (Bola de Función): La bola de función de f: F₂ᵏ → S en u ∈ F₂ᵏ con radio ρ se define como: $B_f(u, \rho) = \{f(u') | u' \in \mathbb{F}_2^k \text{ y } d(u, u') \leq \rho\}$

Definición (Función Localmente (ρ, λ)-Acotada): Se dice que f es una función localmente (ρ, λ)-acotada si para todo u ∈ F₂ᵏ, se satisface |Bf(u, ρ)| ≤ λ.

Condición de Continuidad: Se asume que existe un orden total ≺ en Im(f) tal que cada Bf(u, ρ) forma un bloque contiguo (contiguous block).

2. Mapeo de Coloración (Coloring Mapping)

Idea Central del Lema 1: Para funciones localmente (ρ, λ)-acotadas que satisfacen la condición de continuidad, existe un mapeo Colf: F₂ᵏ → λ tal que para cualesquiera u,v con d(u,v) ≤ ρ y f(u) ≠ f(v), se tiene Colf(u) ≠ Colf(v).

Método de Construcción:

• Sea Im(f) = {y₀ ≺ y₁ ≺ ... ≺ yₑ₋₁}
• Defina γ: Im(f) → λ, γ(yⱼ) = 1 + (j mod λ) (coloración cíclica)
• Defina Colf(u) = γ(f(u))

Dado que cada bola de función es un bloque contiguo de tamaño ≤λ, la coloración cíclica es inyectiva en él, garantizando así la propiedad de separación.

Métodos de Construcción de FCC

Construcción 1: Caso λ=4 (Lema 2)

Función de Codificación: Enc(u) = (u, uₚ), donde uₚ = (u'ₚ)ᵗ, y