permutasjonskoder

Permutasjonskoder er en type feilrettende koder der kodeordene består av permutationer av et sett med n symboler. De brukes i situasjoner der data representeres som en ordnet rekkefølge av distinkte symboler, ikke som et vektor av tall med gjentatte elementer.

En kode C er et delmengde av S_n, den symmetriske gruppen av alle n-permutationer. Avstanden mellom to kodeord kan måles på ulike måter; den vanlige er Hamming-avstanden d_H, som er antallet posisjoner i som er different i to permutationer. Andre distanser som ofte brukes, inkluderer Kendall tau-distanse (antall invendinger som må byttes) og Cayley-distanse (relatert til antall transposisjoner som trengs). Når man bruker d_H, betegnes en PA (permutation array) ofte som et (n, M, d)-PA, hvor M er antall kodeord og d er minste avstand.

Et kort eksempel: For n = 3 kan C = {e, (123), (132)} være et permutationcode. Her representeres kodeordene som en-linee viser e = [1,2,3], (123) = [2,3,1], og (132) = [3,1,2]. Alle par av disse kodeordene har d_H = 3, så minimum avstand er 3.

Type anvendelser inkluderer rank-modulering i flash-minner, hvor informasjon uttrykkes ved rangordningen av celler, og feilkontroll for å korrigere feil i rekkefølgen. Permutasjonskoder studeres også i kombinasjonsteori og informasjonslagring der bare rekkefølgen av symboler er relevant.

Se også: Permutasjons-arrayer, Kendall tau-distanse, Cayley-distanse, Rank-modulering.