A clique-based online algorithm for constructing optical orthogonal codes

• A clique-based online algorithm is proposed to construct optical orthogonal codes (OOCs) of relatively large sizes. The proposed algorithm does not use parameter-specific techniques and hence can be used for different code weight and correlation constraints.
• In the proposed algorithm, the construction of OOCs is reduced to the maximum clique problem based on specially generated graphs, where vertices represent the codewords of an OOC and edges represent the cross-correlation relationships between codeword pairs. In order to overcome the limitation of computer memory for storing large graphs, part of the graph vertices are supposed to arrive sequentially to be fed into the proposed algorithm, and a specially designed evolutionary algorithm is used to find the maximum clique of the current graph when new vertices arrive.
• Experiments are conducted to validate the efficiency of the proposed online algorithm for constructing OOC. The result shows that the proposed algorithm outperforms an offline evolutionary algorithm with guided mutation (EA/G) on constructing OOCs.

An optical orthogonal code (OOC) is a family of binary sequences with good auto- and cross-correlation properties. In the literature, various mathematical tools have been used to construct OOCs with specific parameters. But, to find a complete solution for constructing OOCs with an arbitrary setting of parameters is still difficult at the moment. In this paper, a clique-based online algorithm is proposed to construct OOCs of relatively large sizes. In the proposed algorithm, the construction of OOCs is reduced to the maximum clique problem based on specially generated graphs, where vertices represent the codewords of an OOC and edges represent the cross-correlation relationships between codeword pairs. In order to overcome the limitation of computer memory for storing large graphs, part of the graph vertices are supposed to arrive sequentially to be fed into the proposed algorithm, and a specially designed evolutionary algorithm is used to find the maximum clique of the current graph when new vertices arrive. The proposed algorithm does not use parameter-specific techniques and hence can be used for different code weight and correlation constraints. Experiments show that the proposed algorithm outperforms an offline evolutionary algorithm with guided mutation on constructing OOCs.

Figure optionsDownload as PowerPoint slide