A Novel Split-Radix Fast Algorithm for 2-D Discrete Hartley Transform

Longyu Jiang; Huazhong Shu; Jiasong Wu; Lu Wang; Lotfi Senhadji

inserm-00405223, version 1

A Novel Split-Radix Fast Algorithm for 2-D Discrete Hartley Transform

Longyu Jiang ¹, Huazhong Shu ( Auteur à contacter de préférence ) ^1, 2, Jiasong Wu () ^1, 2, 3, Lu Wang ^1, 2, Lotfi Senhadji () ^2, 3

IEEE Transactions on Circuits and Systems. Part I, Regular Papers 57, 4 (2010) 911-924

Résumé : This paper presents a fast split-radix-(2×2)/(8×8) algorithm for computing the two-dimensional (2-D) discrete Hartley transform (DHT) of length N×N with N = q*2m, where q is an odd integer. The proposed algorithm decomposes an N×N DHT into one N/2×N/2 DHT and forty-eight N/8×N/8 DHTs. It achieves an efficient reduction on the number of arithmetic operations, data transfers and twiddle factors compared to the split-radix-(2×2)/(4×4) algorithm. Moreover, the characteristic of expression in simple matrices leads to an easy implementation of the algorithm. If implementing the above two algorithms with fully parallel structure in hardware, it seems that the proposed algorithm can decrease the area complexity compared to the split-radix-(2×2)/(4×4) algorithm, but requires a little more time complexity. An application of the proposed algorithm to 2-D medical image compression is also provided.

1 : Laboratory of Image Science and Technology (LIST)
SouthEast University – School of Computer Science and Engineering
2 : Centre de Recherche en Information Biomédicale sino-français (CRIBS)
INSERM : LABORATOIRE INTERNATIONAL ASSOCIÉ – Université de Rennes 1 – SouthEast University
3 : Laboratoire Traitement du Signal et de l'Image (LTSI)
INSERM : U642 – Université de Rennes 1

inserm-00405223, version 1
http://www.hal.inserm.fr/inserm-00405223
oai:www.hal.inserm.fr:inserm-00405223
Contributeur : Lotfi Senhadji <>
Soumis le : Lundi 17 Mai 2010, 10:45:07
Dernière modification le : Lundi 17 Mai 2010, 10:45:07

Voir la fiche détaillée

Documents associés

PDF :

DOI : 10.1109/TCSI.2009.2028639

Exporter

Bibtex EndNote TEI RefWorks

%% inserm-00405223, version 1
%% http://www.hal.inserm.fr/inserm-00405223
@article{jiang:inserm-00405223,
    hal_id = {inserm-00405223},
    url = {http://www.hal.inserm.fr/inserm-00405223},
    title = {{A Novel Split-Radix Fast Algorithm for 2-D Discrete Hartley Transform}},
    author = {Jiang, Longyu and Shu, Huazhong and Wu, Jiasong and Wang, Lu and Senhadji, Lotfi},
    abstract = {{This paper presents a fast split-radix-(2×2)/(8×8) algorithm for computing the two-dimensional (2-D) discrete Hartley transform (DHT) of length N×N with N = q*2m, where q is an odd integer. The proposed algorithm decomposes an N×N DHT into one N/2×N/2 DHT and forty-eight N/8×N/8 DHTs. It achieves an efficient reduction on the number of arithmetic operations, data transfers and twiddle factors compared to the split-radix-(2×2)/(4×4) algorithm. Moreover, the characteristic of expression in simple matrices leads to an easy implementation of the algorithm. If implementing the above two algorithms with fully parallel structure in hardware, it seems that the proposed algorithm can decrease the area complexity compared to the split-radix-(2×2)/(4×4) algorithm, but requires a little more time complexity. An application of the proposed algorithm to 2-D medical image compression is also provided.}},
    keywords = {Two-dimensional (2-D) discrete Hartley transform (DHT); split-radix; fast algorithm; data compression},
    language = {Anglais},
    affiliation = {Laboratory of Image Science and Technology - LIST , Centre de Recherche en Information Biom{\'e}dicale sino-fran{\c c}ais - CRIBS , Laboratoire Traitement du Signal et de l'Image - LTSI},
    pages = {911-924},
    journal = {IEEE Transactions on Circuits and Systems. Part I, Regular Papers},
    volume = {57},
    number = {4 },
    note = {This work was supported by the National Natural Science Foundation of China under Grant 60873048, the Program for Changjiang Scholars and Innovative Research Team in University and the Natural Science Foundation of Jiangsu Province of China under Grant BK2008279. },
    audience = {internationale },
    issn = {1549-8328 },
    doi = {10.1109/TCSI.2009.2028639 },
    year = {2010},
    month = Apr,
    pdf = {http://www.hal.inserm.fr/inserm-00405223/PDF/A\_Novel\_Split-Radix\_Fast\_Algorithm\_for\_2-D\_Discrete\_Hartley\_Transform.pdf},
}

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="article"><head>Articles dans des revues avec comité de lecture</head>
<biblStruct type="article" xml:id="inserm-00405223"><analytic>
<author><persName><forename>Longyu</forename><surname>Jiang</surname></persName>
<affiliation>
<orgName type="laboratory">LIST</orgName>
<orgName type="team">Laboratory of Image Science and Technology</orgName>
<country>CN</country>
<orgName type="institution">SouthEast University</orgName>
<orgName type="institution">School of Computer Science and Engineering</orgName>
</affiliation>
</author>
<author><persName><forename>Huazhong</forename><surname>Shu</surname></persName>
<affiliation>
<orgName type="laboratory">LIST</orgName>
<orgName type="team">Laboratory of Image Science and Technology</orgName>
<country>CN</country>
<orgName type="institution">SouthEast University</orgName>
<orgName type="institution">School of Computer Science and Engineering</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">CRIBS</orgName>
<orgName type="team">Centre de Recherche en Information Biomédicale sino-français</orgName>
<country>FR</country>
<orgName type="institution">INSERM : LABORATOIRE INTERNATIONAL ASSOCIÉ</orgName>
<orgName type="institution">Université de Rennes 1</orgName>
<orgName type="institution">SouthEast University</orgName>
</affiliation>
</author>
<author><persName><forename>Jiasong</forename><surname>Wu</surname></persName>
<affiliation>
<orgName type="laboratory">LIST</orgName>
<orgName type="team">Laboratory of Image Science and Technology</orgName>
<country>CN</country>
<orgName type="institution">SouthEast University</orgName>
<orgName type="institution">School of Computer Science and Engineering</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">CRIBS</orgName>
<orgName type="team">Centre de Recherche en Information Biomédicale sino-français</orgName>
<country>FR</country>
<orgName type="institution">INSERM : LABORATOIRE INTERNATIONAL ASSOCIÉ</orgName>
<orgName type="institution">Université de Rennes 1</orgName>
<orgName type="institution">SouthEast University</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">LTSI</orgName>
<orgName type="team">Laboratoire Traitement du Signal et de l'Image</orgName>
<country>FR</country>
<orgName type="institution">INSERM : U642</orgName>
<orgName type="institution">Université de Rennes 1</orgName>
</affiliation>
</author>
<author><persName><forename>Lu</forename><surname>Wang</surname></persName>
<affiliation>
<orgName type="laboratory">LIST</orgName>
<orgName type="team">Laboratory of Image Science and Technology</orgName>
<country>CN</country>
<orgName type="institution">SouthEast University</orgName>
<orgName type="institution">School of Computer Science and Engineering</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">CRIBS</orgName>
<orgName type="team">Centre de Recherche en Information Biomédicale sino-français</orgName>
<country>FR</country>
<orgName type="institution">INSERM : LABORATOIRE INTERNATIONAL ASSOCIÉ</orgName>
<orgName type="institution">Université de Rennes 1</orgName>
<orgName type="institution">SouthEast University</orgName>
</affiliation>
</author>
<author><persName><forename>Lotfi</forename><surname>Senhadji</surname></persName>
<affiliation>
<orgName type="laboratory">CRIBS</orgName>
<orgName type="team">Centre de Recherche en Information Biomédicale sino-français</orgName>
<country>FR</country>
<orgName type="institution">INSERM : LABORATOIRE INTERNATIONAL ASSOCIÉ</orgName>
<orgName type="institution">Université de Rennes 1</orgName>
<orgName type="institution">SouthEast University</orgName>
</affiliation>
<affiliation>
<orgName type="laboratory">LTSI</orgName>
<orgName type="team">Laboratoire Traitement du Signal et de l'Image</orgName>
<country>FR</country>
<orgName type="institution">INSERM : U642</orgName>
<orgName type="institution">Université de Rennes 1</orgName>
</affiliation>
</author>
<title type="main" level="a">A Novel Split-Radix Fast Algorithm for 2-D Discrete Hartley Transform</title></analytic><monogr><title level="j" type="main">IEEE Transactions on Circuits and Systems. Part I, Regular Papers</title><imprint><biblScope type="publicationDate">2010-04-01</biblScope><biblScope type="vol">57</biblScope><biblScope type="issue">4</biblScope><biblScope type="pp">911-924</biblScope></imprint></monogr><idno type="doi">10.1109/TCSI.2009.2028639</idno><idno type="HALid">http://www.hal.inserm.fr/inserm-00405223</idno><idno type="HALFile">http://www.hal.inserm.fr/inserm-00405223/PDF/A_Novel_Split-Radix_Fast_Algorithm_for_2-D_Discrete_Hartley_Transform.pdf</idno></biblStruct>
</listBibl>
</listBibl>