A fixed length code is called immutable if no codeword can be transformed into another codeword by using only a restricted set of symbol changes. Immutablecodes are used to prevent undetectable updates of information stored over write-once memories [14]. In this paper we consider immutablecodes on the alphabet Q={0,..., q−1}. We prove that a maximum size immutablecode of block length n can be obtained by taking the set of all vectors in Q^n of weight ⌈n(q−1)⧸2⌉. Furthermore, we propose an encoding rule to map information sequences of length k into codewords of an immutablecode of length k+p. The number k of information digits and the number p of parity digits must satisfy the inequality k≤2(q^p−1)⧸(q−1)−p. The proposed encoding algorithm has computational complexity O(k).
Efficient q-ary Immutable Codes
GARGANO, Luisa;VACCARO, Ugo
1991-01-01
Abstract
A fixed length code is called immutable if no codeword can be transformed into another codeword by using only a restricted set of symbol changes. Immutablecodes are used to prevent undetectable updates of information stored over write-once memories [14]. In this paper we consider immutablecodes on the alphabet Q={0,..., q−1}. We prove that a maximum size immutablecode of block length n can be obtained by taking the set of all vectors in Q^n of weight ⌈n(q−1)⧸2⌉. Furthermore, we propose an encoding rule to map information sequences of length k into codewords of an immutablecode of length k+p. The number k of information digits and the number p of parity digits must satisfy the inequality k≤2(q^p−1)⧸(q−1)−p. The proposed encoding algorithm has computational complexity O(k).I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
