<p>The fast Walsh-Hadamard transform (WHT) is widely used in signal and image processing for its binary-valued basis. It achieves a low computational complexity of <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$O\left( {Nlog_{2} N} \right)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mfenced close=")" open="("> <mrow> <mi>N</mi> <mi>l</mi> <mi>o</mi> <msub> <mi>g</mi> <mn>2</mn> </msub> <mi>N</mi> </mrow> </mfenced> </mrow> </math></EquationSource> </InlineEquation> by leveraging recursive operations with a butterfly structure. However, its parallel implementation through conventional ad-hoc methods often requires substantial hardware resources. Thus, hardware reduction in conventional parallel architectures remains a challenging task. This paper presents a hardware-efficient design of a single-stage 4-point WHT integrated circuit (IC) that serves as a building block for scalable <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$N$</EquationSource> <EquationSource Format="MATHML"><math> <mi>N</mi> </math></EquationSource> </InlineEquation>-point transforms. Unlike traditional multi-stage architectures, the proposed method restructures the parallel computation into a single-stage, reusing the same hardware via feedback connections to compute all <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$log_{2} N - 1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>l</mi> <mi>o</mi> <msub> <mi>g</mi> <mn>2</mn> </msub> <mi>N</mi> <mo>-</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> stages. This design requires only <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$N/4$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>N</mi> <mo stretchy="false">/</mo> <mn>4</mn> </mrow> </math></EquationSource> </InlineEquation> ICs and significantly reduces hardware usage—by 88.6–97.7%—compared to existing architectures. For 8 and 16-point transforms, it achieves area savings of up to 93.5%, power reduction up to 48.9%, and MCP (multi cycle path) improvement up to 42%, with no loss in parallel processing efficiency. The effectiveness is validated on an Artix-7 FPGA (Field Programmable Gate Array) board using Vivado, and also on an OpenGate 45 nm library cell using the Synopsys Design Compiler.</p>

A Scalable Parallel Architecture for Fast Walsh Hadamard Transform

期刊论文
发表日期：

2026年4月21日

查看全文

Pulak Mazumder,
Kusal Bhattacharyya,
Arghadip Das,
Rathindra Nath Biswas,
Mrinal Kanti Naskar

摘要

The fast Walsh-Hadamard transform (WHT) is widely used in signal and image processing for its binary-valued basis. It achieves a low computational complexity of $O\left( {Nlog_{2} N} \right)$ $O (N l o g_{2} N)$ by leveraging recursive operations with a butterfly structure. However, its parallel implementation through conventional ad-hoc methods often requires substantial hardware resources. Thus, hardware reduction in conventional parallel architectures remains a challenging task. This paper presents a hardware-efficient design of a single-stage 4-point WHT integrated circuit (IC) that serves as a building block for scalable $N$ $N$ -point transforms. Unlike traditional multi-stage architectures, the proposed method restructures the parallel computation into a single-stage, reusing the same hardware via feedback connections to compute all $log_{2} N - 1$ $l o g_{2} N - 1$ stages. This design requires only $N/4$ $N / 4$ ICs and significantly reduces hardware usage—by 88.6–97.7%—compared to existing architectures. For 8 and 16-point transforms, it achieves area savings of up to 93.5%, power reduction up to 48.9%, and MCP (multi cycle path) improvement up to 42%, with no loss in parallel processing efficiency. The effectiveness is validated on an Artix-7 FPGA (Field Programmable Gate Array) board using Vivado, and also on an OpenGate 45 nm library cell using the Synopsys Design Compiler.