Grafos conexos e controle em códigos de treliça

Jorge Arpasi, Edson Carvalho, Leandro Tibola

DOI: 10.14209/sbrt.2008.42127

Evento: XXVI Simpósio Brasileiro de Telecomunicações (SBrT2008)

Keywords: Grafos conexos controle códicos de treliça TCM extensão de grupos Keywords— Connected graphs factor graphs control trellis codes TCM extension of groups

Abstract

A treliça de um código convolucional binário é um grafo conexo, isto é, todos os estados estão conectados por algum caminho formado pela concatenação de transições rotuladas pelos bits de informação codificada. Quando o código convolucional é não-binário, a treliça nem sempre vai ser um grafo conexo. Neste trabalho é mostrado a equivalência entre conexidade de grafos e controlabilidade dos códigos convolucionais de grupo que são gerados a partir de extensões de grupos. Mais precisamente; dado um grupo G como uma extensão U por S, i.e. U × S = G, considere a famı́lia H = {ν : U × S → S ; ν é um homomorfismo sobrejetor}. Cada ν gera um grafo cujo conjunto de vértices é S, e conjunto de arestas é {(s, ν(u, s)), u ∈ U, s ∈ S}. Então para G finito e não abeliano é discutido a existência de alguma extensão U × S = G, S não abeliano, |U | < |S| , e algum 2 ν ∈ H, tais que o grafo seja conexo.

Download