Codici binari ciclici
Salve a tutti,qualcuno sà dirmi come si risolve questo piccolo quesito?
Determinare quanti sono e quante parole contengono,i codici binari ciclici non banali di lunghezza 7.Scrivere se esiste almeno un codice di 2 parole (elencare le parole) diverso da quello a ripetizione.
Grazie a tutti!
Determinare quanti sono e quante parole contengono,i codici binari ciclici non banali di lunghezza 7.Scrivere se esiste almeno un codice di 2 parole (elencare le parole) diverso da quello a ripetizione.
Grazie a tutti!
Risposte
Cosa si intende con codice binario ciclico? Puoi fare un esempio?
Ciao,prima di tutto grazie della risposta,non è specificato niente nel testo,è possibile si tratti di codici di hamming?
Non saprei. Non conosco questi argomenti, credevo fosse qualcosa di immediato.
Direi che è meglio se aspetti qualcuno che ne sa
Direi che è meglio se aspetti qualcuno che ne sa
ti ringrazio
Ciao,
da che corso o librio è tratto questo esercizio?
da che corso o librio è tratto questo esercizio?
ciao,è preso da esercizi (non svolti) del corso di calcolo combinatorio e crittografia.Ti leggo altri esercizi molto simili:
Il codice binario lineare ciclico di lunghezza 7 assegnato tramite il polinomio generatore g(x)=x^3 + x + 1 è un codice M.D.S?Perchè?Codificare in C la sequenza 10000001 conservando i simboli di informazione.
Quanti sono gli (8,6)-codici 5-ari lineari ciclici?Perchè?Verificare se (1,4,0,4,0,0,3,1) è una parola dell'(8,4)-codice C 5-ario lineare ciclico avente h(x) (x+3)(x+4)(x^2 +2) come polinomio di controllo
Quante sono e quante parole contengono i codici non banali lineari ciclici di lunghezza 7.Scrivere il polinomio generatore e quello di controllo del (7,4) codice C binario lineare ciclico contenente la parola (1,1,0,0,1,0,1).Codificare in C(senza utilizzare la matrice generatrice) la sequenza 1010 in modo che i simboli di informazione rimangano inalterati.
Grazie
Il codice binario lineare ciclico di lunghezza 7 assegnato tramite il polinomio generatore g(x)=x^3 + x + 1 è un codice M.D.S?Perchè?Codificare in C la sequenza 10000001 conservando i simboli di informazione.
Quanti sono gli (8,6)-codici 5-ari lineari ciclici?Perchè?Verificare se (1,4,0,4,0,0,3,1) è una parola dell'(8,4)-codice C 5-ario lineare ciclico avente h(x) (x+3)(x+4)(x^2 +2) come polinomio di controllo
Quante sono e quante parole contengono i codici non banali lineari ciclici di lunghezza 7.Scrivere il polinomio generatore e quello di controllo del (7,4) codice C binario lineare ciclico contenente la parola (1,1,0,0,1,0,1).Codificare in C(senza utilizzare la matrice generatrice) la sequenza 1010 in modo che i simboli di informazione rimangano inalterati.
Grazie
ah mah è il tipo il CRC, scusa non mi tornava il nome che hai scritto.
Ok appena ho un attimo ti scrivo qualcosa, se non ti risponde qualcuno prima
Ok appena ho un attimo ti scrivo qualcosa, se non ti risponde qualcuno prima
ti ringrazio!
Ho guardato meglio cosa trattasse questo argomento, ero un po' di fretta dopo pranzo perciò ho letto solo in parte. 
Sì il CRC che dicevo sopra appartiene allo stesso gruppo di codici ciclici correttori o di rilevazione e codifiche polinomiali, ma questo che tratti è qualcosa di più raffinato ed esteso di quanto conosca io. Mi dispiace, pensavo di poterti esser d'aiuto, ma va oltre le mie conoscenze di spiegazione.
L'unica cosa che posso fare è reindizzarti a queste dispense: http://www.dima.unige.it/~niesi/TdC/app05.pdf dove rispondono almeno a due tuoi esercizi. Vedi gli Esempi. sorry
Sì il CRC che dicevo sopra appartiene allo stesso gruppo di codici ciclici correttori o di rilevazione e codifiche polinomiali, ma questo che tratti è qualcosa di più raffinato ed esteso di quanto conosca io. Mi dispiace, pensavo di poterti esser d'aiuto, ma va oltre le mie conoscenze di spiegazione.
L'unica cosa che posso fare è reindizzarti a queste dispense: http://www.dima.unige.it/~niesi/TdC/app05.pdf dove rispondono almeno a due tuoi esercizi. Vedi gli Esempi. sorry
Sia $k=$ un campo finito di $q$ elementi e sia $n\ge 1$. Un codice ciclico su $k$ di
lunghezza $n$ e' per definizione un ideale $C$ nell'anello finito $k[X]$/$(X^n-1)$.
L'ideale $C$ e' generato da un unico divisore monico $f$ di $X^n-1$.
La dimensione di $C$ e' uguale a $n-d$, dove $d$ e' il grado di $f$.
Abbiamo quindi a che fare con un $(n,n-d)$-codice su $\F_q$.
Il numero di "parole" in $C$ e' $q^{n-d}$, il `polinomio generatore' e' $f$
e il "polinomio di controllo" e' $(X^n-1)$/$f$.
Con questo dizionario, i problemi sui codici ciclici diventano problemi
di algebra che riguardano l'anello $k[X]$/$(X^n-1)$.
Per esempio, nella prima domanda abbiamo che $k=\F_2$
e l'anello rilevante e' $\F_2[X]$/$(X^7-1)$. La sua struttura dipende dalla
fattorizzazione di $X^7-1$ in fattori irridicuibili in $\F_2[X]$.
Si ha che
$X^7-1=(X-1)(X^3+X+1)(X^3+X^2+1)$.
Il polinomio $X^7-1$ ha quindi $2\cdot 2\cdot 2=8$ divisori e ci sono
quindi otto codici. I codici "banali" saranno quelli correspondenti ai
divisori "banali" $1$, $X-1$, $X^7-1$ e $(X^7-1)$/$(X-1)$.
I divisori rimanenti sono $X^3+X+1$, $(X-1)(X^3+X+1)$, $X^3+X^2+1$
e $(X-1)(X^3+X^2+1)$. Si tratta di quattro codici di dimensione
rispettivamente $4$, $3$, $4$ e $3$.
Per poter dire a quale $(7,4)$-codice appartiene la parola $v=(1,1,0,0,1,0,1)$,
va scelto un isomorfismo lineare fra $\F_2[X]$/$(X^7-1)$ e $\F_2^7$. Se diciamo
che $v=(1,1,0,0,1,0,1)$ corrisponde al polinomio $X^6+X^5+X^2+1$, allora $v$
appartiene all'ideale generato da $X^3+X^2+1$, perche' $X^6+X^5+X^2+1$ e'
divisibile per $X^3+X^2+1$.
Infine, per codificare $1010$ va deciso chi sono i quattro bit di informazione.
Diciamo che sono i primi quattro coefficienti: quelli di $X^6$, $X^5$, $X^4$ e $X^3$.
Adesso va trovato l'unico polinomio $g$ di grado $\le 2$, tale
che la somma del polinomio $1010000$ $=$ $X^6 + X^4$ con $g$ sia divisibile
per $X^3+X^2+1$. In altre parole, $g$ e' il resto della divisione di $X^6+X^4$ per
$X^3+X^2+1$. Facendo la divisione con il solito algoritmo si trova che
$g=1$. In altre parole, si ha che $g= 0\cdot X^2 + 0\cdot X + 1$ $=$ $001$ e quindi
la codificazione di $1010$ consiste nell'aggiungere la stringha $001$.
Il risultato e' la parola $1010001$.
lunghezza $n$ e' per definizione un ideale $C$ nell'anello finito $k[X]$/$(X^n-1)$.
L'ideale $C$ e' generato da un unico divisore monico $f$ di $X^n-1$.
La dimensione di $C$ e' uguale a $n-d$, dove $d$ e' il grado di $f$.
Abbiamo quindi a che fare con un $(n,n-d)$-codice su $\F_q$.
Il numero di "parole" in $C$ e' $q^{n-d}$, il `polinomio generatore' e' $f$
e il "polinomio di controllo" e' $(X^n-1)$/$f$.
Con questo dizionario, i problemi sui codici ciclici diventano problemi
di algebra che riguardano l'anello $k[X]$/$(X^n-1)$.
Per esempio, nella prima domanda abbiamo che $k=\F_2$
e l'anello rilevante e' $\F_2[X]$/$(X^7-1)$. La sua struttura dipende dalla
fattorizzazione di $X^7-1$ in fattori irridicuibili in $\F_2[X]$.
Si ha che
$X^7-1=(X-1)(X^3+X+1)(X^3+X^2+1)$.
Il polinomio $X^7-1$ ha quindi $2\cdot 2\cdot 2=8$ divisori e ci sono
quindi otto codici. I codici "banali" saranno quelli correspondenti ai
divisori "banali" $1$, $X-1$, $X^7-1$ e $(X^7-1)$/$(X-1)$.
I divisori rimanenti sono $X^3+X+1$, $(X-1)(X^3+X+1)$, $X^3+X^2+1$
e $(X-1)(X^3+X^2+1)$. Si tratta di quattro codici di dimensione
rispettivamente $4$, $3$, $4$ e $3$.
Per poter dire a quale $(7,4)$-codice appartiene la parola $v=(1,1,0,0,1,0,1)$,
va scelto un isomorfismo lineare fra $\F_2[X]$/$(X^7-1)$ e $\F_2^7$. Se diciamo
che $v=(1,1,0,0,1,0,1)$ corrisponde al polinomio $X^6+X^5+X^2+1$, allora $v$
appartiene all'ideale generato da $X^3+X^2+1$, perche' $X^6+X^5+X^2+1$ e'
divisibile per $X^3+X^2+1$.
Infine, per codificare $1010$ va deciso chi sono i quattro bit di informazione.
Diciamo che sono i primi quattro coefficienti: quelli di $X^6$, $X^5$, $X^4$ e $X^3$.
Adesso va trovato l'unico polinomio $g$ di grado $\le 2$, tale
che la somma del polinomio $1010000$ $=$ $X^6 + X^4$ con $g$ sia divisibile
per $X^3+X^2+1$. In altre parole, $g$ e' il resto della divisione di $X^6+X^4$ per
$X^3+X^2+1$. Facendo la divisione con il solito algoritmo si trova che
$g=1$. In altre parole, si ha che $g= 0\cdot X^2 + 0\cdot X + 1$ $=$ $001$ e quindi
la codificazione di $1010$ consiste nell'aggiungere la stringha $001$.
Il risultato e' la parola $1010001$.
ciao prima di tutto grazie del prezioso aiuto,ma riguardo la seconda domanda del primo esercizio come faccio a trovare (se esiste) almeno un codice di 2 parole diverso da quello a ripetizione?Grazie ancora
ok ho trovato la soluzione nelle dispense,che mi ha indicato l'utente hamming.Grazie ancora.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo