%% Antes de processar este arquivo LaTeX (LaTeX2e) deve %% verificar que o arquivo TEMA.cls estah no mesmo %% diretorio. O arquivo TEMA.cls pode ser obtido do %% endereco www.sbmac.org.br/tema. \documentclass{TEMA} \usepackage[brazil]{babel} % para texto em Português %\usepackage[english]{babel} % para texto em Inglês \usepackage[latin1]{inputenc} % para acentuação em Português %\input{P-margin.inf} \usepackage[dvips]{graphics} \usepackage{subfigure} \usepackage{graphicx} \usepackage{epsfig} \usepackage{graphics} \usepackage{amsmath,amsthm,amsfonts,amssymb,amscd} \usepackage{amsmath} \newcommand{\B}{{\tt\symbol{92}}} \newcommand{\til}{{\tt\symbol{126}}} \newcommand{\chap}{{\tt\symbol{94}}} \newcommand{\agud}{{\tt\symbol{13}}} \newcommand{\crav}{{\tt\symbol{18}}} %%%%%%%%%%%%%%% conjuntos (comandos pessoais) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \DeclareRobustCommand{\n}{{\mathbb N}} \DeclareRobustCommand{\z}{{\mathbb Z}} \DeclareRobustCommand{\q}{{\mathbb Q}} \DeclareRobustCommand{\irr}{{\mathbb I}} \DeclareRobustCommand{\irc}{\irr} \DeclareRobustCommand{\r}{{\mathbb R}} \DeclareRobustCommand{\cp}{{\mathbb C}} \DeclareRobustCommand{\ccc}{\cp} \DeclareRobustCommand{\N}{{\pmb\n}} \DeclareRobustCommand{\Z}{{\pmb\z}} \DeclareRobustCommand{\Q}{{\pmb\q}} \DeclareRobustCommand{\Irr}{{\pmb\irr}} \DeclareRobustCommand{\Irc}{\Irr} \DeclareRobustCommand{\R}{{\pmb\r}} \DeclareRobustCommand{\Cp}{{\pmb\cp}} \DeclareRobustCommand{\Ccc}{\Cp} \DeclareRobustCommand{\f}{{\mathbb F}} \DeclareRobustCommand{\k}{{\mathbb K}} \DeclareRobustCommand{\p}{{\mathbb P}} \DeclareRobustCommand{\F}{{\EuScript F}} \DeclareRobustCommand{\L}{{\EuScript L}} \DeclareRobustCommand{\S}{{\EuScript S}} \DeclareRobustCommand{\P}{{\EuScript P}} \newcommand{\C}{\mathcal{C}} \begin{document} %******************************************************** \title {Construção e análise de códigos esféricos com boas taxas binárias\thanks{Trabalho apresentado no Congresso de Matemática Aplicada e Computacional - Sudeste - 2011.}} \author {L. R. B. NAVES% \thanks{ligia.naves@ifrj.edu.br}\,, IFRJ - Instituto Federal do Rio de Janeiro, Campus Volta Redonda, 27213-100, Volta Redonda, RJ, Brasil \\ \\ C. TOREZZAN% \thanks{cristiano.torezzan@fca.unicamp.br.}\,, Faculdade de Ciências Aplicadas, UNICAMP - Universidade Estadual de Campinas, 13484-350, Limeira, SP, Brasil \\ \\ S. I. R. COSTA% \thanks{sueli@ime.unicamp.br.}\,, Departamento de Matemática, UNICAMP - Universidade Estadual de Campinas 13081-970, Campinas, SP, Brasil} \criartitulo \runningheads {Naves, Torezzan e Costa}{Construção e Análise de códigos esféricos com boas taxas binárias} \begin{abstract} {\bf Resumo}. Neste trabalho apresentamos a construção de códigos esféricos que melhoram, em certos casos, o limitante inferior para taxa binária dado por Shannon. Comparamos alguns dos principais códigos esféricos conhecidos, como a relevante construção apresentada recentemente por P. Sol\'e and J.C. Belfiore e também nossa proposta de uma família de códigos esféricos que é construída em camadas de toros e tem bom desempenho para certos parâmetros. {\bf Palavras-chave}. Matemática discreta, Códigos esféricos, taxa binária. \end{abstract} %******************************************************** \newsec{Introdução} Um código esférico é um conjunto finito de pontos sobre a esfera unitária do $\R^n$. Vamos denotar por $\C(M,n,\rho)$ um código sobre a esfera unitária $S^{n-1} \subset \R^n$, com $M$ pontos e distância mínima ao quadrado igual a $\rho$. Em teoria de informação, pontos alocados sobre a superfície de uma esfera unitária são utilizados para a comunicação através de um canal Gaussiano e são a generalização natural para a conhecida modulação \textit{phase shift keying (PSK)}. Para este propósito é desejável maximizar o número de pontos sobre a esfera, além de construir códigos que tenham alguma estrutura adicional que permita lidar com a complexidade de codificação e decodificação. A taxa binária de um código esférico ou taxa de informação é definida por: $$ R := \lim \sup \frac{\log_2(M)}{n}. $$ Em 1959, Chabauty e Shannon \cite{lachaud} apresentaram um limitante inferior para $R$ como função de $\rho$, $$ R(\rho) \geq R_s(\rho):= 1 - (1/2)\log_2(\rho (4-\rho)).$$ Lachaud e Stern, em 1994, mostraram que existem códigos esféricos, construídos em tempo polimonial, cuja taxa binária atinge $R_*(\rho)\geq 0.5 R_S(\rho)$ \cite{lachaud}. P. Sol\'e e J.C. Belfiore, baseados na existência de alguns empacotamentos reticulados apresentaram códigos com taxa igual a $R(\rho) \geq R_L:=-0.5 \log_2(\rho)$ e mostraram que, para pequenos valores de $\rho$, $R_s(\rho) - R_L(\rho) = O(\rho^2)$ \cite{sole}. Neste trabalho apresentamos uma família de códigos esféricos que pode ser construída em tempo linear e tem taxa binária acima do limitante de Shannon para alguns parâmetros não assintoticamente nulos. A construção é baseada \cite{isit2009} que utiliza uma folheação da esfera unitária em toros planares. Este trabalho está dividido da seguinte forma: na seção 2, apresentamos uma rápida revisão sobre a construção de códigos esféricos em camadas de toros, baseados em \cite{isit2009} e \cite{tese}; na seção 3, apresentamos uma maneira de escolher os toros e também de preenchê-los que possibilita a construção em tempo linear; na seção 4, apresentamos um comparativo entre nossa construção e os limitantes mencionados anteriormente. A contribuição deste trabalho consiste na maneira como os toros são escolhidos. %deverão ser encaminhados em CD(s) (com uma cópia impressa em %papel A4) ao endereço: \\ %[1.3ex] %\hspace*{1.3cm}TEMA/Fluxo Contínuo \\% %\hspace*{1.3cm}SBMAC \\ % %\hspace*{1.3cm}a/c Prof. Dr. Edson Wendland \\ %\hspace*{1.3cm}Caixa Postal 668 \\ %\hspace*{1.3cm}13560-970 São Carlos, SP.\\[1.3ex] %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %deverão ser encaminhados em CD(s) (com uma cópia impressa em %papel A4) a endereço: \\[1.3ex] %% %\hspace*{1.3cm}TEMA/Seleta do CNMAC \\% %\hspace*{1.3cm}SBMAC \\ % %\hspace*{1.3cm}a/c Prof. Dr. Edson Wendland \\ %\hspace*{1.3cm}Caixa Postal 668 \\ %\hspace*{1.3cm}13560-970 São Carlos, SP.\\[1.3ex] %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %Para ambos os casos, a carta de encaminhamento deve conter nome, %endereço completo e, se possível, endereço eletr\^{o}nico e %telefone do {\bf autor responsável} pela remessa. %******************************************************** \newsec{Códigos esféricos em camadas de toros} %\setcounter{equation}{0} Dada uma dimensão $k\geq 2$ e $\rho \in (0, 2]$, $\rho=d^2$, seja $\C(k, \rho)$ um código esférico k-dimensional qualquer, com distância mínima ao quadrado maior ou igual a $\rho$. O código esférico em camadas de toros denotado por $\C_T(2k,\rho)$ é construído em 2 etapas, como segue \cite{isit 2009} e \cite{tese}: \begin{itemize} \item{Selecionamos os pontos em $\C(k, \rho)$ que possuem somente coordenadas não negativas. Vamos denotar este subcódigo por $\C(k, \rho)_+$. Cada ponto $c \in \C(k, \rho)_+$ define um toro planar $T_c$ na esfera unitaria $S^{2k-1}$. É interessante que $\C(k, \rho)_+$ tenha boa densidade em $S^{k-1}$ e, se possível, alguma propriedade algébrica ou geométrica. Para este propósito, podemos considerar um $\C_T (k, \rho)$ ou qualquer código esférico k-dimensional conhecido. } \item{Para cada toro $T_c$ definido por $\C(k, \rho)_+$, determinamos um conjunto finito de pontos $Y_{T_c}$ com $Y_{T_c} \subset P_c$, para $P_c=\{x \in \R^k: 0\leq x_i \leq 2\pi c_i\}$, tal que $\|\Phi_c(y) - \Phi_c(x)\| \geq d \text{ } \forall x, y \in Y_{T_c}$. Onde $$\Phi_c(y)=(c_1 (cos (\frac{y_1}{c_1}), sen (\frac{y_1}{c_1})), \ldots, c_k (cos (\frac{y_k}{c_k}), sen (\frac{y_k}{c_k}))).$$ Uma boa opção para $Y_{T_c}$ consiste em considerar pontos de algum reticulado $k-$ dimensional conhecido.} \end{itemize} %\centering \begin{figure}[h] \centering \epsfig{file=toronovocirc.eps,height=5cm,width=11cm} \caption{Construção de toro planar em dimensão $4$. } \end{figure} Pode-se demonstrar \cite{isit2009} que, sejam $T_b $ e $T_c$ dois toros planares, para $b$ e $c$ vetores unitários com coordenadas não negativas. A distância mínima entre estes toros é dada por: $$d(T_b,T_c)=\|c-b\|= (\sum^k_{i=1}(c_i-b_i)^2)^{1/2}.$$ A distância entre dois pontos no mesmo toro $T_c$ é dada por: $$d(\Phi_c(u),\Phi_c(v))=2 (\sum^k_{i=1}c_i^2 sen^2(\frac{u_i-v_i}{2c_i}))^{1/2}$$ e é limitada em termos de $\|u-v\|$. Seja $c=(c_1,c_2,\ldots,c_k)$, $\|c\|=1$, e sejam $u, v \in P_c$. Seja $d_k=\|u-v\|$ e $d_{2k}=\|\Phi_c(u)-\Phi_c(v)\|$. Então $$ \frac{2}{\pi}d_k \leq \frac{sen \frac{d_k}{2c_\xi}}{\frac{d_k}{2c_\xi}}\leq d_{2k} \leq \frac{sen \frac{d_k}{2}}{\frac{d_k}{2}}\leq d_k $$ onde $\xi=arg min_i (c_i)$ \cite{isit2009}. Existe, portanto, uma deformação na distância quando saímos do $P_c \subset \R^k$ para o $T_c \subset \R^{2k}$. \begin{figure}[h] \centering \epsfig{file=distances-1.eps,height=5cm,width=11cm} \caption{As distâncias na construção de códigos esféricos em camadas de toros.} \end{figure} \pagebreak %******************************************************** \newsec{Construção e análise de códigos esféricos} Sejam $e_i$ o i-ésimo vetor canônico do $\R^k$, $e=(1,1,\ldots,1) \in \R^k$ e $t>0$. Seja $c_i(t)= \frac{e_i+te}{\|e_i+te\|}$, tal que $c_{ij}>0$, cada vetor $c_i(t)$ define um toro planar sobre $S^{2k-1}$. Podemos estabelecer então o seguinte resultado. \begin{propTEMAp} Para cada $\rho$, $0<\rho<2$, há ao menos $k$ vetores unitários em $S^{k-1}$, com coordenadas positivas, tais que o quadrado da distância entre dois destes vetores é maior que $\rho$. \end{propTEMAp} \begin{proof} Pela definição acima, há $k$ vetores $c_i(t) \in \R^k $. A distância ao quadrado entre vetores do tipo $c_i(t)$ supracitado é dada por: $$|c_i(t)-c_j(t)\|^2=\frac{2}{kt^2+2t+1}$$ onde a equação $\frac{2}{kt^2+2t+1}=\rho$ tem sempre uma solução real positiva dada por $\bar{t}(\rho)=\frac{-\rho+ \sqrt{\rho(k(2-\rho)+\rho)}}{k\rho}$. Seja $c_{min}$ a menor coordenada de $c_i(\bar{t})$, a imagem da aplicação $\Phi$ de qualquer conjunto discreto no interior da caixa $P_{c_i(\bar{t})}$ com distância mínima $d_k \geq 2 c_{min} arcsen \frac{\sqrt{\rho}}{2c_{min}}$ será um código esférico em $S^{2k-1}$ com distância mínima ao quadrado $\rho$. \end{proof} Para cada um dos k toros definidos por $c_i(\bar{t})$ consideramos os pontos do reticulado obtido reescalando o reticulado $D_k$ para que este atinja a distância mínima ao quadrado $\rho$ no interior da caixa $P_{c_i(\bar{t})}$. Como todos os vetores $c_i$ são simétricos por permutações cíclicas de suas coordenadas, é suficiente construir uma camada do código e tomar as permutações cíclicas das coordenadas dos pontos encontrados para obter todo o código. Como um exemplo desta construção considere $k=3$ e $\rho=(0,3)^2$. Neste caso teremos $\bar{t}=2.34719$ e três toros definidos pelos vetores $c_1(\bar{t})=(0.710045, 0.497913,$\\ $0.497913)$, $c_2(\bar{t})=(0.497913, 0.710045, 0.497913)$ e $c_3(\bar{t})=(0.497913, 0.497913,$\\ $0.710045)$. Temos $d_k=0.304734$ e podemos considerar um reticulado reescalado de $D_3$ pelo fator $d_k/\sqrt{2}$. As palavras código em cada um dos três toros serão dadas pela imagem de $\Phi_{c_i}$ do reticulado $\frac{d_k}{\sqrt{2}}D_3$ na caixa $P_{c_i(\bar{t})}$. Neste caso, cada toro terá 1605 pontos e teremos 4815 pontos no código esférico. A taxa binária deste código é $R=2.03889$. Para estes parâmetros, os limitantes de Shannon e de Solé \& Belfiore são respectivamente, 1.75338 e 1.73697. %Na figura 3 apresentamos uma comparação entre os limitantes de Shannon e de Solé \& Belfiore e alguns códigos construídos com nossa aproximação. %\centering %\begin{center} %\includegraphics[scale=0.55]{grafico} %\end{center} %\begin{center} %Figura 3. Comparação entre alguns códigos esféricos construídos em \cite{ICMCTA2011}, os limitantes para taxa binária (Shannon: curva contínua. Solé: curva pontilhada) e uma possível região atingível (em vermelho). %\end{center} %\vskip 20pt Esse tipo de código pode ser facilmente construído, além de ter boa taxa binária para alguns parâmetros e ter baixa complexidade de codificação e decodificação. Entretanto podemos perder desempenho em termos do número máximo de pontos. Na tentativa de obtermos resultados ainda melhores, propomos uma construção que toma sucessivas camadas de vetores unitários no $\R^k$ para definir os toros, ao invés de uma única camada como foi feito. Isso permite, em geral, aumentar o número de pontos no código para um valor fixado de $\rho$ sem comprometer demasiadamente a complexidade de construção. \newsec{Construção de códigos esféricos por vetores unitários em camadas sucessivas} Para construir um código $\C_T(2k, \rho)$ em camadas sucessivas tomaremos vetores unitários com distância $\sqrt{\rho}$ pertencentes a um determinado hiperplano $\Pi_1: x_1+x_2+\ldots+x_k= \alpha$. Cada um desses vetores dará origem a um toro. Para obtermos mais pontos consideraremos um hiperplano $\Pi_2$ paralelo a $\Pi_1$ e distante deste o valor $\sqrt{\rho}$. Logo o novo plano $\Pi_2$ será: $\Pi_2: x_1+x_2+\ldots+x_k=\alpha \pm \sqrt{k \rho}$. Neste novo plano tomaremos, se possível, vetores unitários com coordenadas positivas, os quais distem entre si $\sqrt{\rho}$. Teremos assim mais toros e um número maior de pontos no $\C_T(2k, \rho)$. Prosseguimos assim sucessivamente enquanto houverem planos paralelos a $\Pi_{i+1}$, distantes de $\Pi_i$ o valor $\sqrt{\rho}$, que forneçam vetores unitários com coordenadas positivas. Exemplificando com o caso em que $k=3$, podemos visualizar alguns planos tomados nessa construção. Teremos como planos extremos o plano $x_1+x_2+x_3=1$ e o plano tangente a esfera $S^2$ dado por $x_1+x_2+x_3=\sqrt{3}$. A figura 3 ilustra esse caso. Teremos um limite para o número de planos dado por: $$l_{\Pi}=\left\lfloor \frac{d((1/k,1/k,\ldots,1/k),(1/sqrt{k}, 1/sqrt{k}, \ldots, 1/\sqrt{k}))}{\sqrt{\rho}}\right\rfloor.$$ \begin{figure}[h] \centering \epsfig{file=Fatia.eps,height=4cm,width=4cm} \caption{Esfera $S^2$ e planos com vetores unitários com coordenadas positivas.} \end{figure} \pagebreak Foram construídos alguns códigos partindo de vários vetores no $\R^3$, não necessariamente simétricos, mas todos com coordenadas positivas e provenientes de diferentes planos. Cada vetor gerou um toro e depois, cada toro plano tri-dimensional foi preenchido com pontos do reticulado $D_3$. O resultado foram códigos esféricos no $\R^6$ com boa taxa binária para distâncias não muito pequenas, conforme os dados da tabela sugerem e conforme ilustra o gráfico. \begin{table}[h] \caption{Comparação entre as taxas binárias de códigos esféricos no $\R^6$ com limitantes inferiores para várias distâncias mínimas.}\vspace*{0.2cm} \centering \begin{tabular}{|c|c|c|c|c|} \hline d & M & \text{Taxa} & \text{Shannon} & \text{Patric} \\ \hline 0.5 & 194. & 1.26665 & 1.04655 & 1. \\ \hline 0.4 & 997. & 1.66024 & 1.35137 & 1.32193 \\ \hline 0.3 & 7357. & 2.14082 & 1.75338 & 1.73697 \\ \hline 0.2 & 81095. & 2.71789 & 2.32918 & 2.32193 \\ \hline 0.1 & $3.50004\times 10^6$ & 3.62316 & 3.32373 & 3.32193 \\ \hline 0.01 & $4.30642\times 10^{11}$ & 6.44128 & 6.64387 & 6.64386\\ \hline \end{tabular} \end{table} %\pagebreak \begin{figure}[h] \centering \epsfig{file=graph-1.eps,height=7cm,width=10cm} \caption{Comparação entre alguns códigos esféricos construídos (pontos isolados) e os limitantes para taxa binária (Shannon: curva contínua. Solé: curva pontilhada) em função de $\rho$.} \end{figure} \pagebreak \newsec{Conclusão} Apresentamos uma construção de códigos esféricos em tempo linear para dimensões pares, a qual supera, em algumas dimensões e para distância mínima não muito pequena, o limitante inferior de Shannon para a taxa binária. Essa construção é baseada na folheação da esfera unitária por toros planares, como proposto em \cite{tese}, entretanto com a utilização de sucessivas camadas de vetores unitários no $\R^k$ para definir os toros. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{abstract} {\bf Abstract}.This paper presents a construction of spherical codes and improve, in some cases, the lower bound for binary rate given by Shannon. We compare some of the main spherical codes known as the relevant construction recently presented by P. Solé and J.C. Belfiore and also our proposal from a family of spherical codes which is constructed based on the foliation of unit sphere by flat torus and performs well for certain parameters. \end{abstract} \begin{thebibliography}{8} \bibitem{BergerGostiaux} M. Berger, and B. Gostiaux, ``Differential Geometry: Manifolds, Curves and Surfaces''. Springer-Verlag, Berlin, 1988. \bibitem{sloane} J.H. Conway, N.J.A. Sloane, ``Sphere packings, lattices and groups'', Springer Verlag, GMW 290, 2003. \bibitem{CMAP:2004} S. I. R. Costa, M.M. Alves, E. Agustini, and R. Palazzo, ``Graphs, tesselations and perfect codes on flat tori'', IEEE Transactions on Information Theory, vol. 50, pp. 2363-2377, Oct. 2004. \bibitem{ericson} T. Ericson, V. Zinoviev, ``Codes on Euclidean spheres'', North-Holland, Amsterdam, 2001. \bibitem{lachaud} G. Lachaud, J. Stern, ``Polynomial-time construction of codes. II Spherical codes and the kissing number of spheres'', IEEE Trans. Inform. Theory 40, 1994, n 4, 1140 - 1146. \bibitem{tese} C. Torezzan, ``Códigos esféricos em toros planares'', Tese de doutorado, IMECC-Unicamp, 2009. %\bibitem{ICMCTA2011} %C. Torezzan, S. I. R. Costa, ``Linear time constructive spherical codes with good binary rates'', Submetido. \bibitem{isit2009} C. Torezzan, S. I. R. Costa, \& V. A. Vaishampayan, ``Spherical codes on torus layers'', International Symposium on Information Theory, Seul, Coreia, 2009. \bibitem{sole} P. Sol\'e, J.C. Belfiore, ``Constructive spherical codes near the Shannon bound'', The Seventh International Workshop on Coding and Cryptography 2011, Paris, França. \end{thebibliography} \end{document} \newpage $ \ \ $ \thispagestyle{myheadings} \markboth{ }{ }