Uso de backtracking para generación de sucesiones sonares
Abstract
In a frequency hopping radar system, the signal consists of one or more frequencies chosen from a set of m available frequencies for transmission at each of a set of n consecutive time intervals. Such a signal can be represented by an m X n matrix of 0’s and 1’s in which each column contains exactly one 1. When the signal is reflected back to the observer, it is shifted in both time and frequency. The amounts of these shifts can be used to determine both distance and velocity. The amounts of shifts, in turn, are determined by comparing all shifts of a replica of the transmitted signal with the signal received. This is equivalent to counting the number of coincidences of 1s in a shifted version of the matrix of 0’s and 1’s that represents the signal. The number of such hits as a function of shifts in time and frequency is called the auto-correlation function. A sonar array is a m x n pattern which has at most one hit in its auto-correlation function. In a multiple target environment, one pattern is sent for each target. In this work we study algorithms that generate sonar type sequences for one and multiple target recognition. The use of backtracking technique to find sonar sequences is presented as a particular case.
Downloads
References
[2] R. Gagliardi, J. Robbins, y H. Taylor, “Acquisition sequences in PPM communications,” IEEE Trans. Inform. Theory, vol. IT-33, pp. 738-744, 1987
[3] R. A Games, “An algebraic construction of sonar sequences using M-sequences,” SIAM J. Algebraic Discrete Methods, vol. 8, pp. 753 – 761, Octubre 1987
[4] S. W. Golomb,L. Baumert, “Backtrack Programming,” Journal of the ACM (JACM), vol. 12, pp. 516-524, 1965
[5] S. W. Golomb, “Algebraic constructions for Costas arrays,” J. Combinatorial Theory, Ser. A, vol. 37, pp. 13-21, 1984
[6] S. W. Golomb y H. Taylor, “Two-dimensional synchronization patterns for minimum ambiguity,” IEEE Trans. Inform. Theory, vol. IT-28, pp. 263-272, Julio 1982
[7] S. W. Golomb y H. Taylor, “Constructions and properties of Costas arrays,” Proc. IEEE, vol. 72, pp. 1143-1163, Septiembre 1984
[8] S.V. Maric y E. L. Titlebaum, “A class of Frequency Hop Codes with Nearly Ideal Characteristics for Use in Multiple Access Spread Spectrum Communications and Radar and Sonar System,” en IEEE Transactions on Communications, Septiembre 1992
[9] O. Moreno, S Maric “Classes of Costas and Sonar Sequences For Multi-target Recognition,” en IEEE ISIT 1997
[10] O. Moreno, S Maric and LiYuchun “Best Know Sonar Sequences for Multi-target Recognition. In IEEE ISIT 1997
[11] O. Moreno y R. A. Games, “Sonar Sequences from Costas Arrays and the Best Known Sonar Sequences with up to 100 Symbols,” IEEE Trans. Inform. Theory, vol. 39, NO. 6, pp. 1985-1987, Noviembre 1993
[12] O. Moreno. S.V. Maric, “A Class of Frequency Hop Codes with Nearly Ideal Characteristics for Multipletarget Recognition. In thirty-third Annual Allerton Conference on Communication, Control, and Computing, Octubre 1995
[13] O. Moreno, P. Pei and J. Ramirez, A Parallel Algorith for Enumeration of Costas, In proceedings of the 7th SIAM Conference on Paralllel Conference Processing for Scientific Computing pp. 255-260, 1995
[14] O.Moreno, J. Ramirez, D. Bollman, y E. Orozco, “Faster algorithms for the generation of Symmetry-Invariant Permutations”, Marzo de 2002 [15] E. Orozco, “On the parallel generation of coastal arrays,” Tesis, University of Puerto Rico,1998
