Sobre a complexidade da decodificação por esfera em comunicações digitais

A decodificação por esfera foi sugerida por vários autores como um algoritmo eficiente para resolver vários problemas de detecção em comunicações digitais. Em alguns casos, o algoritmo é referido como um algoritmo de complexidade polinomial sem especificar claramente quais suposições são feitas sobre a estrutura do problema. Outra alegação é que, embora a complexidade no pior caso seja exponencial, a complexidade esperada do algoritmo é polinomial. Aqui, estudamos a complexidade esperada em que o tamanho do problema é definido como o número de símbolos detectados conjuntamente, e nosso principal resultado é que a complexidade esperada é exponencial para uma relação sinal-ruído (SNR) fixa, ao contrário de alegações anteriores. O raio da esfera, que é um parâmetro do algoritmo, deve ser escolhido para garantir uma probabilidade não nula de resolver o problema de detecção. Isso causa a complexidade exponencial, visto que o quadrado do raio deve crescer linearmente com o tamanho do problema. A taxa de aumento linear é, no entanto, dependente da variância do ruído e, portanto, a taxa da função exponencial é fortemente dependente da SNR. Portanto, a decodificação por esfera pode ser eficiente para certos valores de SNR e problemas de tamanho moderado, embora o número de operações exigidas pelo algoritmo, a rigor, sempre cresça como uma função exponencial do tamanho do problema.