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

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).
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11386/3136574
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 18
  • ???jsp.display-item.citation.isi??? 16
social impact