An Iterative Algorithm and Low Complexity Hardware Architecture for Fast Acquisition of Long PN Codes in UWB Systems | Journal of Signal Processing Systems Skip to main content
Springer Nature Link
Log in

An Iterative Algorithm and Low Complexity Hardware Architecture for Fast Acquisition of Long PN Codes in UWB Systems

  • Published:
Journal of VLSI signal processing systems for signal, image and video technology Aims and scope Submit manuscript

Abstract

Rapidly acquiring the code phase of the spreading sequence in an ultra-wideband system is a very difficult problem. In this paper, we present a new iterative algorithm and its hardware architecture in detail. Our algorithm is based on running iterative message passing algorithms on a standard graphical model augmented with multiple redundant models. Simulation results show that our new algorithm operates at lower signal to noise ratio than earlier works using iterative message passing algorithms. We also demonstrate an efficient hardware architecture for implementing the new algorithm. Specifically, the redundant models can be combined together so that substantial memory usage can be reduced. Our prototype achieves the cost-speed product unachievable by traditional approaches.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. M.K. Simon, J.K. Omura, R.A. Scholtz, and B.K. Levitt, Spread Spectrum Communications Handbook, McGraw-Hill, 1994.

  2. K.M. Chugg and M. Zhu, “A New Approach to Rapid PN Code Acquisition using Interative Message Passing Techniques,” IEEE J. Select. Areas Commun., vol. 23, no. 51, June 2005.

  3. E.A. Homier and R.A. Scholtz, “Rapid Acquisition of Ultra-Wideband Signals in the Dense Multipath Channel,” in Digest of Papers, IEEE Conference on Ultra Wideband Systems and Technologies, May 2002, pp. 105–109.

  4. M. Zhu and K.M. Chugg, “Iterative Message Passing Techniques for Rapid PN code Acquisition,” in Proc. IEEE Military Comm. Conf., Boston, MA, October 2003, pp. 434–439.

  5. I.D. O'Donnell, S.W. Chen, B.T. Wang, and R.W. Brodersen, “An Integrated, Low Power, Ultra-Wideband Reansceriver Architecture for Low-Rate, Indoor Wireless Systems,” IEEE CAS Workshop on Wireless Communications and Networking, September 2002.

  6. A. Polydoros and C.L. Weber, “A Unified Approach to Serial Search Spread-Spectrum Code Acquisition,” IEEE Trans. Commununication, vol. 32, pp. 542–560, 1984.

    Article  Google Scholar 

  7. L. Yang and L. Hanzo, “Iterative Soft Sequential Estimation Assisted Acquisition of m-Sequence,” IEE Electronics Letters, vol. 38, no. 24, 2002, pp. 1550–1551.

    Article  Google Scholar 

  8. R.G. Gallager, “Acquisition of I-Sequences Using Recursive Soft Sequential estimation,” IEEE Trans. Commununication, vol. 52, no. 2, Feb 2004 pp. 199–204.

    Article  Google Scholar 

  9. B. Vigoda, J. Dauwels, N. Gershenfeld, and H. Loeliger, “Low-Complexity lfsr Synchronization by Forward-only Message Passing,” IEEE Trans. Information Theory, June 2003, submitted.

  10. S.W. Golomb, Shift Register Sequences revised edition. Aegean Park Press, 1982.

  11. C. Berrou, A. Glavieux, and P. Thitmajshima, “Near Shannon Limit Error-Correcting Coding and Decoding: Turbo-Codes,” in Proc. International Conf. Communications, Geneva, Switzerland, pp. 1064–1070, 1993.

  12. C. Berrou and A. Glavieux, “Near Optimum Error Correcting Coding and Decoding: Turbo-Codes,” IEEE Trans. Commununication, vol. 44, no. 10, pp. 1261–1271, October 1996.

    Article  Google Scholar 

  13. R.G. Gallager, “Low Density Parity Check Codes,” IEEE Trans. Information Theory, vol. 8, January 1962 pp. 21–28.

    Article  MathSciNet  MATH  Google Scholar 

  14. R.G. Gallager, Low-Density Parity-Check Codes. MIT Press, Cambridge, MA, 1963.

    Google Scholar 

  15. D.J.C. MacKay and R.M. Neal, “Near Shannon Limit Performance of Low Density Parity Check Codes,” IEE Electronics Letters, vol. 32, no. 18, August 1996 pp. 1645–1646.

    Article  Google Scholar 

  16. N. Wiberg, Codes and Decoding on General Graphs, Ph.D. dissertation, Linköping University (Sweden), 1996.

  17. R.J. McEliece, D.J.C. MacKay, and J.F. Cheng, “Turbo Decoding as an Instance of Pearl's “Belief Propagation” Algorithm,” IEEE J. Select. Areas Commun., vol. 16, February 1998, pp. 140–152.

    Article  Google Scholar 

  18. S.M. Aji, “Graphical Models and Iterative Decoding,” Ph.D. dissertation, California Institute of Technology, 1999.

  19. S.M. Aji and R.J. McEliece, “The Generalized Distributive Law,” IEEE Trans. Information Theory, vol. 46, no. 2, pp. 325–343, March 2000.

    Article  MathSciNet  MATH  Google Scholar 

  20. F. Kschischang, B. Frey, and H.-A. Loeliger, “Factor Graphs and the Sum-Product Algorithm,” IEEE Trans. Information Theory, vol. 47, Feb. 2001, pp. 498–519.

    Article  MathSciNet  MATH  Google Scholar 

  21. K.M. Chugg, A. Anastasopoulos, and X. Chen, Iterative Detection: Adaptivity, Complexity Reduction, and Applications. Kluwer Academic Publishers, 2001.

  22. S. Benedetto and G. Montorsi, “Design of Parallel Concatenated Convolutional Codes,” IEEE Trans. Commununication, vol. 44, May 1996, pp. 591–600.

    Article  MATH  Google Scholar 

  23. S. Benedetto, D. Divsalar, G. Montorsi, and F. Pollara, “Serial Concatenation of Interleaved Codes: Performance Analysis, Design, and Iterative Decoding,” IEEE Trans. Information Theory, vol. 44, no. 3, May 1998, pp. 909–926.

    Article  MathSciNet  MATH  Google Scholar 

  24. R.M. Tanner, “A Recursive Approach to Low Complexity Codes,” IEEE Trans. Information Theory, vol. IT-27, September, pp. 533–547, 1981.

    Article  MathSciNet  Google Scholar 

  25. S. Benedetto, D. Divsalar, G. Montorsi, and F. Pollara, “Soft-Input Soft-Output Modules for the Construction and Distributed Iterative Decoding of Code Networks,” European Trans. Telecommun., vol. 9, no. 2, March/April, pp. 155–172, 1998.

    Article  Google Scholar 

  26. J.S. Yedidia, J. Chen, and M. Fossorier, “Generating Code Representations Suitable for Belief Propagation Decoding,” in Proc. 40-th Allerton Conference Commun., Control, and Computing, Monticello, IL., October 2002.

  27. N. Santhi and A. Vardy, “On the Effect of Parity-Check Weights in Iterative Decoding,” in Proc. IEEE Internat. Symp. Information Theory, Chicago, IL., July 2004, p. 322.

  28. M. Schwartz and A. Vardy, “On the Stopping Distance and the Stopping Redundancy of Codes,” IEEE Trans. Information Theory, 2005, submitted.

  29. L.R. Bahl, J. Cocke, F. Jelinek, and J. Raviv, “Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate,” IEEE Trans. Information Theory, vol. IT-20, 1974, pp. 284–287.

    Article  MathSciNet  Google Scholar 

  30. A.J. Viterbi, “Justification and Implementation of the MAP Decoder for Convolutional Codes,” IEEE J. Select. Areas Commun., vol. 16, February 1998, pp. 260–264.

    Article  Google Scholar 

  31. G. Masera, G. Piccinini, M.R. Roch, and M. Zamboni, “VLSI Architectures for Turbo Codes,” IEEE Trans. VLSI, vol. 7, no. 3, 1999.

    Google Scholar 

  32. J. Dielissen and J. Huisken, “State Vector Reduction for Initialization of Sliding Windows MAP,” in 2nd Internation Symposium on Turbo Codes & Related Topics, Brest, France, 2000, pp. 387–390.

  33. S. Yoon and Y. Bar-Ness, “A Parallel MAP Algorithm for Low Latency Turbo Decoding,” IEEE Communications Letters, vol. 6, no. 7, 2002, pp. 288–290.

    Article  Google Scholar 

  34. A. Abbasfar and K. Yao, “An Efficient and Practical Architecture for High Speed Turbo Decoders,” in IEEE 58th Vehicular Technology Conference, Vol. 1, 2003, pp. 337–341.

    Google Scholar 

  35. A.P. Hekstra, “An Alternative to Metric Rescaling in Viterbi Decoders,” IEEE Trans. Commununication, vol. 37, no. 11, November 1989.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Electrical Engineering, Viterbi School of Engineering, Communication Science Institute, University of Southern California, Los Angeles, CA, 90089-2565

    On Wa Yeung & Keith M. Chugg

Authors
  1. On Wa Yeung
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Keith M. Chugg
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to On Wa Yeung.

Additional information

This work was supported in part by the Army Research Office DAAD19-01-1-0477 and the National Science Foundation CCF-0428940.

On Wa Yeung received the B. Eng. degree in Electronic Engineering from the Chinese University of Hong Kong, Hong Kong in 1994 and MSEE from the University of Southern California (USC) in 1996. In 1997–2003, he was a hardware engineer in Hughes Network Systems, San Diego, CA, designing hardware platforms for fixed wireless and satellite terminals. He is currently working towards the Ph.D. degree in EE at USC. His research interests are in the areas of iterative detection algorithms and their hardware implementation.

Keith M. Chugg (S'88-M'95) received the B.S. degree (high distinction) in Engineering from Harvey Mudd College, Claremont, CA in 1989 and the M.S. and Ph.D. degrees in Electrical Engineering (EE) from the University of Southern California (USC), Los Angeles, CA in 1990 and 1995, respectively. During the 1995–1996 academic year he was an Assistant Professor with the Electrical and Computer Engineering Dept., The University of Arizona, Tucson, AZ. In 1996 he joined the EE Dept. at USC in 1996 where he is currently an Associate Professor. His research interests are in the general areas of signaling, detection, and estimation for digital communication and data storage systems. He is also interested in architectures for efficient implementation of the resulting algorithms. Along with his former Ph.D. students, A. Anastasopoulos and X. Chen, he is coauthor of the book Iterative Detection: Adaptivity, Complexity Reduction, and Applications published by Kluwer Academic Press. He is a co-founder of TrellisWare Technologies, LLC, where he is Chief Scientist. He has served as an associate editor for the IEEE Transactions on Communications and was Program Co-Chair for the Communication Theory Symposium at Globecom 2002. He received the Fred W. Ellersick award for the best unclassified paper at MILCOM 2003.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Yeung, O.W., Chugg, K.M. An Iterative Algorithm and Low Complexity Hardware Architecture for Fast Acquisition of Long PN Codes in UWB Systems. J VLSI Sign Process Syst Sign Image Video Technol 43, 25–42 (2006). https://doi.org/10.1007/s11265-006-7278-y

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11265-006-7278-y

Keywords

Search

Navigation