A Finite Precision Block Floating Point Treatment to Direct Form, Cascaded and Parallel FIR Digital Filters
This paper proposes an efficient finite precision block floating point (BFP) treatment to the fixed coefficient finite impulse response (FIR) digital filter. The treatment includes effective implementation of all the three forms of the conventional FIR filters, namely, direct form, cascaded and par- allel, and a roundoff error analysis of them in the BFP format. An effective block formatting algorithm together with an adaptive scaling factor is pro- posed to make the realizations more simple from hardware view point. To this end, a generic relation between the tap weight vector length and the input block length is deduced. The implementation scheme also emphasises on a simple block exponent update technique to prevent overflow even during the block to block transition phase. The roundoff noise is also investigated along the analogous lines, taking into consideration these implementational issues. The simulation results show that the BFP roundoff errors depend on the sig- nal level almost in the same way as floating point roundoff noise, resulting in approximately constant signal to noise ratio over a relatively large dynamic range.
[1] C. W. Barnes and S. Shinnaka, "Finite Word Effects in Block-state
Realizations of Fixed Point Digital Filters," IEEE Trans. Circuits Syst.,
vol CAS-27, pp. 345-349, May 1980
[2] P. H. Bauer, "Absolute Error Bounds for Block-Floating-Point Direct-
Form Digital Filters," IEEE Trans. Signal Processing, vol. 43, no. 8,
pp. 1994-1996, Aug. 1995.
[3] R. N. Bracewell, "The Fast Hartley Transform," Proc. IEEE, vol. 72,
no. 8, pp. 1010-1018, Aug. 1984.
[4] C. Caraiscos and B. Liu, "A Roundoff Error Analysis of the LMS
Adaptive Algorithm," IEEE Trans. Acoust., Speech, Signal Processing,
vol. ASSP-32, no. 1, pp. 34-41, Feb. 1984.
[5] C. Caraiscos, "Implementation Issues in Digital Signal Processing,"
Ph.D. dissertation, Princeton University, Jan. 1984.
[6] D. S. K. Chan and L. R. Rabiner, "Analysis of Quantization Errors in the
Direct Form for Finite Impulse Response Digital Filters," IEEE Trans.
Audio Electroaccoust., vol. AU-21, no. 4, pp. 354-366, Aug. 1973.
[7] D. S. K. Chan and L. R. Rabiner, "Theory of Roundoff Noise in Cascade
Realizations of Finite Impulse Response Digital Filters," Bell Syst. Tech.
J., vol. 52, no. 3, pp. 329-345, Mar. 1973.
[8] D. S. K. Chan and L. R. Rabiner, "An Algorithm for Minimizing Round-
off Noise in Cascade Realizations of Finite Impulse Response Digital
Filters," Bell Syst. Tech. J., vol. 52, no. 3, pp. 347-385, Mar. 1973.
[9] D. J. DeFatta, J. G. Lucas andW. S. Hodgkiss, Digital Signal Process-
ing: A System Design Approach. New York: Wiley, 1990.
[10] P. M. Ebert, J. E. Mazo, and M. G. Taylor, "Overflow oscillations in
digital filters," Bell Sys. Tech. J., vol. 48, pp. 2999{3020, 1969.
[11] A. Erickson and B. Fagin, "Calculating FHT in Hardware," IEEE Trans.
Signal Processing, vol. 40, no. 4, pp. 1341-1353, June 1992.
[12] B. Gold and C. M. Rader, Digital Processing of Signals. New York:
Mcgraw-Hill, 1969.
[13] J. R. Heath, H. T. Nagle, Jr., and S. G. Shiva, "Realization of Digi-
tal Filters using Input-Scaled Floating-Point Arithmetic," IEEE Trans.
Acoust., Speech, Signal Processing, vol. ASSP-27, no. 5, pp. 469-477,
Oct. 1979.
[14] P. Henrici, Partial Fractions, volume 1 of "Applied and Computational
Complex Analysis," Chapter 7. Wiley, 1974.
[15] O. Hermann and H. W. Schuessler, "On the Accuracy Problem in the
Design of Nonrecursive Digital Filters," Arch. Elek. Ubertragung, vol.
24, pp. 525-526, 1970.
[16] L. B. Jackson, "Beginnings: The First Hardware Digital Filters," IEEE
Signal Proc. Magazine, vol. 21, no. 6, pp. 55-81, Nov. 2004.
[17] L. B. Jackson, Digital Filters and Signal Processing, 3rd ed. Boston,
MA: Kluwer, 1996.
[18] L. B. Jackson, "Roundoff-Noise Analysis for Fixed-Point Digital Filters
Realized in Cascade or Parallel Form," IEEE Trans. Audio Electroa-
coust., vol. AE-18, no. 2, pp. 107-122, June 1970.
[19] L. B. Jackson, J. F. Kaiser and H. S. McDonald, "An Approach to the
Implementation of Digital Filters," IEEE Trans. Audio Electroacoust.,
vol. AE-16, no. 3, pp. 413-421, Sept. 1968.
[20] T. Kailath, "A View of Three Decades of Linear Filtering Theory," IEEE
Trans. Inform. Theory, vol. IT-20, pp. 146-181, March 1974.
[21] J. F. Kaiser, "Digital Filters," in System Analysis by Digital Computer,
J.F Kaiserand F.F Kuo, Eds New York: wiley, 1966, pp. 218-285
[22] K. Kalliojarvi and J.Astola, "Roundoff Errors in Block-Floating-Point
Systems," IEEE Trans. Signal Processing, vol. 44, no. 4, pp. 783-790,
April 1996.
[23] D. M. Kodek, "Performance Limit of Finite Wordlength FIR Digital
FJuilltyer2s0,"05IE. EE Trans. Signal Processing, vol. 53, no. 7, pp. 2462-2469,
[24] D. M. Kodek, "Design of Optimal Finite Wordlength FIR Digital Filters
using Integer Programming Techniques," IEEE Trans. Acoust., Speech,
Signal Processing, vol. ASSP-28, June 1980.
[25] W.Li and A.M. Peterson "Block Z Transform and Its Application
to FIR Filtering," IEEE Trans. Signal Processing, vol. 39, no. 10, pp.
2335-2343, Oct. 1991.
[26] Y. C. Lim and S. R. Parker, "Discrete coefficient FIR digital filter design
based upon an LMS criteria," IEEE Trans. Circuits Syst., vol. CAS-30,
[27] Ypp. .C7.2L3i-m73a9n,dOSc.t.R1.9P8a3r.ker, "FIR filter design over a discrete powers of
two coefficient space," IEEE Trans. Acoust., Speech, Signal Processing,
vol. ASSP-31, pp. 583-590, June 1983.
[28] B. Liu and T. Kaneko, "Error Analysis of Digital Filters Realized in
Floating-Point Arithmetic," IEEE Proc., vol. 57, pp. 1735-1747, Oct.
1969.
[29] M. Martinez-Peiro et. al. (2002, February). FPGA Based
FIR Filters using Distributed Arithmetic (Online). Available:
http://www.techonline.com/community/ed resource/feature article/20135.
[30] A. Mitra, et. al., "A Block Floating Point Treatment to the LMS Algo-
rithm: Efficient Realization and Roundoff Error Analysis," IEEE Trans.
Signal Processing, vol. 53, no. 12, pp. 4536-4544, Dec. 2005.
[31] A. Mitra, "On Finite Wordlength Properties of Block Floating Point
Arithmetic," Int. J. Signal Processing, vol. 2, no. 2, pp. 120-125, July
2005.
[32] A. Mitra, "A New Block-based NLMS Algorithm and Its Realization
in Block Floating Point Format," Int. J. Info. Tech., vol. 1, no. 4, pp.
244-248, Dec. 2004.
[33] A. Mitra, "A New Way of Implementation and Associated Round-
off Noise Analysis of Fixed Coefficient FIR Digital Filters Employing
Block-Floating-Point Arithmetic," in Proc. 3rd IEEE Benelux Signal
Processing Symposium (SPS 2002), Leuven, Belgium, March 21-22,
2002, pp. 113-116.
[34] S. K. Mitra, Digital Signal Processing: A Computer-based Approach.
New York: Mcgraw-Hill, 2001.
[35] A. V. Oppenheim and R. W. Schafer, Discrete-Time Signal Processing.
Englewood Cliffs, NJ: Prentice-Hall, 1989.
[36] A. V. Oppenheim and R. W. Schafer, Digital Signal Processing. En-
glewood Cliffs, NJ: Prentice-Hall, 1975.
[37] A. V. Oppenheim and C. Weinstein, "Effects of finite register length in
digital filtering and the fast Fourier transform," Proc. IEEE, vol. 60, pp.
957-976, Aug. 1972.
[38] A. V. Oppenheim, "Realization of digital filters using block floating
point arithmetic," IEEE Trans. Audio Electroacoust., vol. AE-18, no. 2,
pp. 130-136, June 1970.
[39] L. R. Rabiner and B. Gold, Theory and Applications of Digital Signal
Processing. Englewood Cliffs, NJ: Prentice-Hall, 1976.
[40] L. R. Rabiner, "The Design of Finite Impulse Response Digital Filters
using Linear Programming Techniques," Bell Syst. Tech. J., vol. 21, pp.
1177-1198, July-Aug. 1972.
[41] K. R. Ralev and P. H. Bauer, "Realization of Block Floating Point
Digital Filters and Application to Block Implementations," IEEE Trans.
Signal Processing, vol. 47, no. 4, pp. 1076-1086, April 1999.
[42] S. Sridharan and G. Dickman, "Block floating point implementation of
digital filters using the DSP56000," Microprocess. Microsyst., vol. 12,
no. 6, pp. 299-308, July-Aug. 1988.
[43] F. J. Taylor, "Block Floating Point Distributed Filters," IEEE Trans.
Circuits Syst., vol. CAS-31, pp. 300-304, Mar. 1984.
[44] M. Waters et. al., "Parallel Interconnection of Cascaded Subfilters: Im-
proved Performance at High Order," in Proc. IEEE Int. Symp. Circuits,
Syst. (ISCAS), Hong Kong, June 9-12, 1997, pp. 2216-2219.
[45] C. Weinstein and A. V. Oppenheim, "A Comparison of Roundoff Noise
in Fixed Point and Floating Point Digital Filter Realizations," Proc.
IEEE, vol. 57, pp. 1181-1183, Aug. 1969.
[46] C. Weinstein, "Quantization Effects in Frequency Sampling Filters,"
NEREM Record, 222, New York: Lewis Winner, 1968.
[1] C. W. Barnes and S. Shinnaka, "Finite Word Effects in Block-state
Realizations of Fixed Point Digital Filters," IEEE Trans. Circuits Syst.,
vol CAS-27, pp. 345-349, May 1980
[2] P. H. Bauer, "Absolute Error Bounds for Block-Floating-Point Direct-
Form Digital Filters," IEEE Trans. Signal Processing, vol. 43, no. 8,
pp. 1994-1996, Aug. 1995.
[3] R. N. Bracewell, "The Fast Hartley Transform," Proc. IEEE, vol. 72,
no. 8, pp. 1010-1018, Aug. 1984.
[4] C. Caraiscos and B. Liu, "A Roundoff Error Analysis of the LMS
Adaptive Algorithm," IEEE Trans. Acoust., Speech, Signal Processing,
vol. ASSP-32, no. 1, pp. 34-41, Feb. 1984.
[5] C. Caraiscos, "Implementation Issues in Digital Signal Processing,"
Ph.D. dissertation, Princeton University, Jan. 1984.
[6] D. S. K. Chan and L. R. Rabiner, "Analysis of Quantization Errors in the
Direct Form for Finite Impulse Response Digital Filters," IEEE Trans.
Audio Electroaccoust., vol. AU-21, no. 4, pp. 354-366, Aug. 1973.
[7] D. S. K. Chan and L. R. Rabiner, "Theory of Roundoff Noise in Cascade
Realizations of Finite Impulse Response Digital Filters," Bell Syst. Tech.
J., vol. 52, no. 3, pp. 329-345, Mar. 1973.
[8] D. S. K. Chan and L. R. Rabiner, "An Algorithm for Minimizing Round-
off Noise in Cascade Realizations of Finite Impulse Response Digital
Filters," Bell Syst. Tech. J., vol. 52, no. 3, pp. 347-385, Mar. 1973.
[9] D. J. DeFatta, J. G. Lucas andW. S. Hodgkiss, Digital Signal Process-
ing: A System Design Approach. New York: Wiley, 1990.
[10] P. M. Ebert, J. E. Mazo, and M. G. Taylor, "Overflow oscillations in
digital filters," Bell Sys. Tech. J., vol. 48, pp. 2999{3020, 1969.
[11] A. Erickson and B. Fagin, "Calculating FHT in Hardware," IEEE Trans.
Signal Processing, vol. 40, no. 4, pp. 1341-1353, June 1992.
[12] B. Gold and C. M. Rader, Digital Processing of Signals. New York:
Mcgraw-Hill, 1969.
[13] J. R. Heath, H. T. Nagle, Jr., and S. G. Shiva, "Realization of Digi-
tal Filters using Input-Scaled Floating-Point Arithmetic," IEEE Trans.
Acoust., Speech, Signal Processing, vol. ASSP-27, no. 5, pp. 469-477,
Oct. 1979.
[14] P. Henrici, Partial Fractions, volume 1 of "Applied and Computational
Complex Analysis," Chapter 7. Wiley, 1974.
[15] O. Hermann and H. W. Schuessler, "On the Accuracy Problem in the
Design of Nonrecursive Digital Filters," Arch. Elek. Ubertragung, vol.
24, pp. 525-526, 1970.
[16] L. B. Jackson, "Beginnings: The First Hardware Digital Filters," IEEE
Signal Proc. Magazine, vol. 21, no. 6, pp. 55-81, Nov. 2004.
[17] L. B. Jackson, Digital Filters and Signal Processing, 3rd ed. Boston,
MA: Kluwer, 1996.
[18] L. B. Jackson, "Roundoff-Noise Analysis for Fixed-Point Digital Filters
Realized in Cascade or Parallel Form," IEEE Trans. Audio Electroa-
coust., vol. AE-18, no. 2, pp. 107-122, June 1970.
[19] L. B. Jackson, J. F. Kaiser and H. S. McDonald, "An Approach to the
Implementation of Digital Filters," IEEE Trans. Audio Electroacoust.,
vol. AE-16, no. 3, pp. 413-421, Sept. 1968.
[20] T. Kailath, "A View of Three Decades of Linear Filtering Theory," IEEE
Trans. Inform. Theory, vol. IT-20, pp. 146-181, March 1974.
[21] J. F. Kaiser, "Digital Filters," in System Analysis by Digital Computer,
J.F Kaiserand F.F Kuo, Eds New York: wiley, 1966, pp. 218-285
[22] K. Kalliojarvi and J.Astola, "Roundoff Errors in Block-Floating-Point
Systems," IEEE Trans. Signal Processing, vol. 44, no. 4, pp. 783-790,
April 1996.
[23] D. M. Kodek, "Performance Limit of Finite Wordlength FIR Digital
FJuilltyer2s0,"05IE. EE Trans. Signal Processing, vol. 53, no. 7, pp. 2462-2469,
[24] D. M. Kodek, "Design of Optimal Finite Wordlength FIR Digital Filters
using Integer Programming Techniques," IEEE Trans. Acoust., Speech,
Signal Processing, vol. ASSP-28, June 1980.
[25] W.Li and A.M. Peterson "Block Z Transform and Its Application
to FIR Filtering," IEEE Trans. Signal Processing, vol. 39, no. 10, pp.
2335-2343, Oct. 1991.
[26] Y. C. Lim and S. R. Parker, "Discrete coefficient FIR digital filter design
based upon an LMS criteria," IEEE Trans. Circuits Syst., vol. CAS-30,
[27] Ypp. .C7.2L3i-m73a9n,dOSc.t.R1.9P8a3r.ker, "FIR filter design over a discrete powers of
two coefficient space," IEEE Trans. Acoust., Speech, Signal Processing,
vol. ASSP-31, pp. 583-590, June 1983.
[28] B. Liu and T. Kaneko, "Error Analysis of Digital Filters Realized in
Floating-Point Arithmetic," IEEE Proc., vol. 57, pp. 1735-1747, Oct.
1969.
[29] M. Martinez-Peiro et. al. (2002, February). FPGA Based
FIR Filters using Distributed Arithmetic (Online). Available:
http://www.techonline.com/community/ed resource/feature article/20135.
[30] A. Mitra, et. al., "A Block Floating Point Treatment to the LMS Algo-
rithm: Efficient Realization and Roundoff Error Analysis," IEEE Trans.
Signal Processing, vol. 53, no. 12, pp. 4536-4544, Dec. 2005.
[31] A. Mitra, "On Finite Wordlength Properties of Block Floating Point
Arithmetic," Int. J. Signal Processing, vol. 2, no. 2, pp. 120-125, July
2005.
[32] A. Mitra, "A New Block-based NLMS Algorithm and Its Realization
in Block Floating Point Format," Int. J. Info. Tech., vol. 1, no. 4, pp.
244-248, Dec. 2004.
[33] A. Mitra, "A New Way of Implementation and Associated Round-
off Noise Analysis of Fixed Coefficient FIR Digital Filters Employing
Block-Floating-Point Arithmetic," in Proc. 3rd IEEE Benelux Signal
Processing Symposium (SPS 2002), Leuven, Belgium, March 21-22,
2002, pp. 113-116.
[34] S. K. Mitra, Digital Signal Processing: A Computer-based Approach.
New York: Mcgraw-Hill, 2001.
[35] A. V. Oppenheim and R. W. Schafer, Discrete-Time Signal Processing.
Englewood Cliffs, NJ: Prentice-Hall, 1989.
[36] A. V. Oppenheim and R. W. Schafer, Digital Signal Processing. En-
glewood Cliffs, NJ: Prentice-Hall, 1975.
[37] A. V. Oppenheim and C. Weinstein, "Effects of finite register length in
digital filtering and the fast Fourier transform," Proc. IEEE, vol. 60, pp.
957-976, Aug. 1972.
[38] A. V. Oppenheim, "Realization of digital filters using block floating
point arithmetic," IEEE Trans. Audio Electroacoust., vol. AE-18, no. 2,
pp. 130-136, June 1970.
[39] L. R. Rabiner and B. Gold, Theory and Applications of Digital Signal
Processing. Englewood Cliffs, NJ: Prentice-Hall, 1976.
[40] L. R. Rabiner, "The Design of Finite Impulse Response Digital Filters
using Linear Programming Techniques," Bell Syst. Tech. J., vol. 21, pp.
1177-1198, July-Aug. 1972.
[41] K. R. Ralev and P. H. Bauer, "Realization of Block Floating Point
Digital Filters and Application to Block Implementations," IEEE Trans.
Signal Processing, vol. 47, no. 4, pp. 1076-1086, April 1999.
[42] S. Sridharan and G. Dickman, "Block floating point implementation of
digital filters using the DSP56000," Microprocess. Microsyst., vol. 12,
no. 6, pp. 299-308, July-Aug. 1988.
[43] F. J. Taylor, "Block Floating Point Distributed Filters," IEEE Trans.
Circuits Syst., vol. CAS-31, pp. 300-304, Mar. 1984.
[44] M. Waters et. al., "Parallel Interconnection of Cascaded Subfilters: Im-
proved Performance at High Order," in Proc. IEEE Int. Symp. Circuits,
Syst. (ISCAS), Hong Kong, June 9-12, 1997, pp. 2216-2219.
[45] C. Weinstein and A. V. Oppenheim, "A Comparison of Roundoff Noise
in Fixed Point and Floating Point Digital Filter Realizations," Proc.
IEEE, vol. 57, pp. 1181-1183, Aug. 1969.
[46] C. Weinstein, "Quantization Effects in Frequency Sampling Filters,"
NEREM Record, 222, New York: Lewis Winner, 1968.
@article{"International Journal of Electrical, Electronic and Communication Sciences:61498", author = "Abhijit Mitra", title = "A Finite Precision Block Floating Point Treatment to Direct Form, Cascaded and Parallel FIR Digital Filters", abstract = "This paper proposes an efficient finite precision block floating point (BFP) treatment to the fixed coefficient finite impulse response (FIR) digital filter. The treatment includes effective implementation of all the three forms of the conventional FIR filters, namely, direct form, cascaded and par- allel, and a roundoff error analysis of them in the BFP format. An effective block formatting algorithm together with an adaptive scaling factor is pro- posed to make the realizations more simple from hardware view point. To this end, a generic relation between the tap weight vector length and the input block length is deduced. The implementation scheme also emphasises on a simple block exponent update technique to prevent overflow even during the block to block transition phase. The roundoff noise is also investigated along the analogous lines, taking into consideration these implementational issues. The simulation results show that the BFP roundoff errors depend on the sig- nal level almost in the same way as floating point roundoff noise, resulting in approximately constant signal to noise ratio over a relatively large dynamic range.
", keywords = "Finite impulse response digital filters, Cascade structure, Parallel
structure, Block floating point arithmetic, Roundoff error.", volume = "1", number = "6", pages = "885-9", }
