Gauss整环上的二维AFT算法

D0I:10.13374/j.issn1001-053x.1996.06.021 第18卷第6期 北京科技大学学报 VoL18 No.6 1996年12月 Journal of University of Science and Technology Beijing Dec.1996 Gauss整环上的二维AFT算法 陈兆斗”陈难先2)葛锡金2) 1)北京科技大学数力系，北京1000832)北京科技大学应用物理研究所 摘要利用整环上的M6bius反演公式，给出了Gauss整环上的二维Fourier系数的AFT算法，其 方法同样适用于小波级数的系数计算， 关键词AFT算法，Mδbius反演公式，Gauss整环，梳状8函数 中图分类号0156.2,0174.22 1前人工作回顾 设fx)以2π为周期，并有二阶连续导数，其Fourier级数展开式为： x)=∑Cnem (1) n=-oo 则当n是自然数且C。=0时有： k*0 利用Mobius反演公式可得： C+c=芝45=29三 (2) 其中u(k)为数论中的M6bius函数. 当k=1 ()=(-1)‘ 当k为t个互不相同的素数之积 (3) 1o 当k含有平方因子 这种利用M6bius反演公式计算Fourier系数的方法，l988年Tufts和Sadasiv发现这种算法具 有计算较简单、易于在计算机上实现并行处理的特点四，在很多方面优于快速Fourier变换 (FFT),并将这种算法命名为AFT(Arithmetic Fourier Transform). 由于图像处理的需要，Tufs等人在文献[2]中已经开始了与二维AFT算法有关的讨 论.设x,y)分别关于x,y以2π为周期的函数，其Fourier级数展开式为： k)=艺Cn,c+n m.n (4) m,n=-0 在以往的研究中，关于二维Fourier系数的AFT算法都是用一维AFT算法依次重复.尽 1996-06-25收稿第一作者男46岁副教授硕士 ·国家自然科学基金资助项目

第 卷 第 期 年 月 北 京 科 技 大 学 学 报 整 环上 的二 维 算法 ‘ 陈 兆斗 ’ 陈难先 葛锡金 北京科技大学 数力系 ， 北京 北京科技大学应用 物理研究所 摘要 利 用 整 环上 的 反 演公 式 ， 给 出 了 整 环上 的二 维 系数 的 算法 ， 其 方 法 同样适用 于小 波级数 的系数计算 关键词 算法 ， 反 演公式 ， 整 环 ， 梳状 函数 中图分类号 。 一 ， 前人工作 回顾 设 力 以 为周 期 ， 并 有 二 阶连续 导数 ， 其 丽 级数展 开式 为 力 艺 风 “ 则 当 。 是 自然 数且 一 时有 二 乏一 。 。 上 夸刀丝绎、 冲渭 厂 “ 利 用 反 演公 式 可得 川 一 户 的 认鳄 办邻 其 中 风 为数论 中的 函 数 一 ‘ 当 当 为 个互 不相 同的 素数之 积 当 含有 平方 因子 一 ‘、了 拜 这种利 用 反 演 公 式计算 系数 的方 法 ， 年 和 发现 这种算 法具 有 计 算 较 简 单 、 易 于 在 计 算 机 上 实 现 并 行 处 理 的 特 点 ， 在 很 多 方 面 优 于 快 速 变 换 ， 并将 这种算 法命名 为 由于 图像 处 理 的 需 要 ， 等 人 在 文 献 〔 中 已 经 开 始 了 与 二 维 · 算 法 有 关 的讨 论 设 方 ，力分别 关于 ， 以 兀 为周 期 的 函数 ， 其 级 数展 开式 为 十 力 ， 一 。 ， 。 歹 一 吼 ， · ’ ‘ “ 砂， 在 以 往 的研 究 中 ， 关 于 二 维 系数 的 算 法 都是 用 一 维 算 法 依 次重 复 尽 一 一 收稿 第一作者 男 岁 副教授 硕 士 申 国家 自然科学 基 金 资助项 目 DOI ：10．13374／j ．issn1001－053x．1996．06．021

Vol.18 No.6 陈兆斗等：Gauss整环上的二维AFT算法 ·591 管系数Cm的表达形式不同，但归纳起来这些算法在计算遇到的问题是当C。+0或Cm。+0 时，一维AFT算法将难以处理，必须假定它们都为0.这样就不可能使二维AFT算法在 Fourier系数的计算中得到应用.可见，二维AFT算法的理论尚不完善，本文的工作是较完善 地解决了这个问题. 2基本公式和符号 设K是复数域中含有数1的非空子集，对于乘法构成唯一分解半群，U是K中所有单位 元组成的非空子集，称为单位集.以下均假定K是可列集，U中元素是有限的.对于a,bEK,若 存在ceK使得a=bc,则称b整除a,记为bla.若bla且alb则称a,b是相伴的，记为a~b, 这时存在eeU使得a=be. 对任何aeK,aU有既约分解： a=pp (5) 其中εEU,k≥1，P,是K中互不相伴的既约元(i=1,2,…,).在相伴的意义下分解式(5)是唯 一的.K上的Mobius函数定义为： 当aeU -1) 当aEU且式(5)中k=k2=…=k,=1 (6) 0 当a含有平方因子 由于相伴元只相差一个单位因子，所以当a与b相伴时4(@)=4(b),即相伴元的Mobius函数 值相等 【定理1】唯一分解半群上的Mobius反演公式 设Fa,Ha是定义在K上的函数，单位集U={e1e2,…,eN}.如果对任何ceK恒有： He)=Fae) (7) 并且级数∑F(abc)绝对收敛，则对任何cEK有M6bius反演公式： a,bEK Rced+rce,)+…+ceJ=4aMa） (8) 其中u(a)是K上的M6bius函数，见文献[3]. 【定理2】梳状6函数的公式 三e=2n芝a0e-2m (9) 见文献[4】. 3 Gauss整环上的二维AFT算法 文中约定二维Fourier级数(4)式中的系数Cmh由下式确定： Cy)emdx dy (10)

陈兆斗等 整 环上 的二 维 算法 管 系数 气 ，。 的表达形 式不 同 ， 但 归纳起来这些算法 在计算遇 到 的 问题是 当 。 羊 或 气 ， 。 羊 时 ， 一 维 算 法 将 难 以 处 理 ， 必 须 假 定 它 们 都 为 这 样 就 不 可 能 使 二 维 算 法 在 系 数 的计 算 中得 到 应 用 可 见 ， 二 维 算 法 的理 论 尚不 完善 本 文 的工 作是 较 完善 地解 决 了 这个 问题 基本公式和符号 设 是 复 数域 中含 有数 的非 空 子集 ， 对于乘 法 构 成 唯 一分解 半 群 ， 是 中所有 单位 元 组成 的非 空 子集 ， 称 为单位集 以 下 均假定 是 可 列集 ， 中元 素是 有 限 的 对于 “ ， ‘ ， 若 存 在 ‘ 使得 “ ， 则 称 整 除 ， 记 为 若 且 则 称 ， 是 相 伴 的 ， 记 为 “ 一 ， 这 时存在 ￡ ‘ 使得 瓦 · 对任何 ， 必 有 既 约分解 口 一 。 尸 尸全… 尸介 其 中 ， 气七 ， ‘ 是 中互 不相 伴 的既 约元 ， ， …， · 在相 伴 的意 义下 分解 式 是 唯 一 的 上 的 函数定 义 为 ， ·，一 一 ， ， 当 当 “ 偌 且 式 中 ， 气 … 二 凡二 当 含有 平 方 因子 由于相 伴元 只 相 差一 个单位 因子 ， 所 以 当 “ 与 相 伴 时 风 风 ， 即相 伴元 的 函数 值相 等 【定理 唯 一分解 半 群 上 的 反 演公 式 设 月 ， 是 定义在 上 的 函 数 ， 单位集 一 ￡ ， 。 ，… ，￡、 · 如果 对任何 。 ‘ 恒有 乏 并且 级 数 艺 绝对收敛 ， 则 对任何 。 〔 有 反 演公 式 ， ‘ ， 月 … 凡 ￡户一 去叉 拭 二 ， 口 〔 式 其 中 拜 是 上 的 函数 ， 见 文 献 【 【定理 梳状 函 数 的公 式 艺 淞 二 艺 一 二 见 文 献 】 整环上 的二维 算法 文 中约定 二 维 级数 式 中的系 数 气 ， 、 由下 式 确 定 气 ， 。 一 命去从 ，，。 一 ’ ‘ 即

·592· 北京科技大学学报 1996年No.6 其中D=[0,2π)×[0,2π)，i=√-1，并假定实函数x,y)有连续的2rr≥2)阶偏导数，且 60=0. 设G={a+bi:a,b∈Z},其中i=V-1,Z是整数集.G中元素关于复数的乘法和加法 构成整环，称为Gauss整环，G中的元素称为Gauss整数，G·表示G中非零的Gauss整数的集 合，则G·关于复数的乘法构成唯一分解半群，其单位集U={±1，±i}含4个元素.对任何 非零的Gauss整数a,则a,-a,ia,-ia是相伴的，它们的模相等，幅角相差π/2的整数倍.文 献[6]给出了G*中既约元的判断方法.在G*上可定义Mobius函数.需注意由于(1+) ×(1-)=-i(1+)2=2,(1+i)是既约元，所以a(2)=0,而自然数中2的M6bius函数值 为-1. 式(4)中的Fourier系数，用Gauss整数进行标号，记C。=C,其中a=m+nieG.以下 约定B=a+bi.对于任何aEG·,利用广义函数的理论及梳状6函数的公式(9)可推出： 气C。制器e咖mx =<川品.ea+e-+d -1+三dmr+w-2p08(-au+g-2pjry -三m+-2g-+刚-2gjt (11) 取变换： u=mx ny,v=-nx my (12) 这个变换将区域D变为D,由于a∈G*,变换的Jacobian行列式恰为： m n n m =m2+n2=|a2*0 (13) 逆变换为： x =(mu-nv)/la,y=(nu+mv)a2 (14) 于是， (15) 由于D是有界集，当pl,9充分大后，式(15)中相应的项为0.这样式(15)中的和式是有限 和.于是， 9.-京点功 (16) 其中，D(a)=Da)∩D,D(a)={(2n(mp-nq)Ia2,2r(p+mq)Ia):p,9eZ· 可以看到D@)是由a唯一确定的有限点集，它是D(a)在D中的子集，并称之为采样点 集，可以证明，当≥2时对任何aG~级数点.C绝对收敛曲定理1，使用G~上的

北 京 科 技 大 学 学 报 年 其 中 一 ，幻 ，幻 ， 一 召二万 ， 并 假 定 实 函数 方 ， 有 连续 的 叹 七 阶偏 导数 ， 且 写 ， 。 · 设 。 。 ， ‘ ， 其 中 抓万 ， 是 整 数集 中元 素关于 复数 的乘法 和 加法 构成整 环 ， 称 为 整 环 ， 中的元素称 为 整 数 ’ 表示 中非零 的 整 数 的集 合 ， 则 ’ 关于 复数的乘法 构成 唯 一分解半群 ， 其单位集 士 ， 士 含 个元 素 对任何 非零 的 整 数 ， 则 ， 一 ， ， 一 是 相 伴 的 ， 它们 的模相 等 ， 幅角相 差 兀 的整数倍 文 献 给 出 了 ’ 中 既 约 元 的 判 断 方 法 在 ’ 上 可 定 义 函 数 需 注 意 由 于 一 一 ， 是 既 约元 ， 所 以 解 ， 而 自然数 中 的 函数值 为 一 式 中的 系数 ， 用 整 数进行标号 ， 记 一 吼 。 ， 其 中 一 十 ‘ 以下 约定 声 对于 任何 ’ ， 利 用 广义 函数 的理论及梳状 占函数 的公式 可 推 出 一鹿与 一 命去加 ， 少 艺 一 ’ 一 “ 十 ’ 十 “ ” 妙 山 声“ ’ 一 命去加， 〔 艺 一 运 十 动 一 飒 一 “ 耐 吞‘ 一 命去加 ， 一 兀 ， 艺 一 助兀 一 一 汀 山 办 一 。 〔 一 ， ， 。 蔓 二 丁工 ‘ · ， 一 ，“ 一 ‘ 一 ’啊冷功“ 办 取变换 ， 、了了、 门， 一 阴少 这个变换将 区域 变 为 。 · 由于 〔 ’ ， 变换的 刀之 一 力 行列 式恰 为 羊 。 逆变 换 为 一 ， 夕 于 是 ， 一 俞’ ， 艺一 山 丁 。 一 、 ‘ 一 。 · 爪“ 一 刀 刀“ 功 ’ 办 由于 是 有 界 集 ， 当 回 ， 充 分 大 后 ， 式 中相 应 的项 为 · 这 样 式 中的和 式 是 有 限 和 于是 ， 一 裔 叉 力 ， 、 ’一 ’ ， 州 其 中 ， 一 门 ， 户 二 呷 一 。 。 ，， 二 即 。 ， 户 ， 。 〔 可 以 看 到 是油 唯 一 确 定 的有 限 点集 ， 它 是 户 在 中的 子 集 ， 并 称之 为采 样 点 集 可 以 证 明 ， 当 全 时 ， 对 任 何 ‘ ， 级 数 又 。 绝 对 收 敛 由定 理 ， 使 用 上 的 八 ‘ 不 ’

Vol.18 No.6 陈兆斗等：Gauss整环上的二维AFT算法 ·593· M6bius反演公式得到： ++c:+c。超0渠器点 2Σx,) (17) 其中4是G"上的Mobius函数. 从几何的观点可以清楚地看到采样点集的结构.平行线族Io:mx+y-2pm=0,pEZ与 1,:-nx+my-2qπ=0，q∈Z分别是等距的平行线族，两条相邻平行线间距离dn=2r/1a. 线族L。与，是相互正交的，它们将平面划分为一系列正方形网络，网格的交点即为D(α)中的 点， 由S。的定义可推出：当B与a相伴时，S。=Se=S_a=S-a,又由于相伴元的Mobius函 数值相等，所以可以把级数(17)中对的求和限制在第一象限内：0≤argB<π/2，即a≥1， b≥0.于是级数(17)可以表示为： C.+C+C+C。品=22+b3n (18) a=1b=0 特别当x,》关于x和y都是偶函数时，C。=C。=C-a=C-c由式(17)，C。的计算将会十 分简单： 的。运2e+8w C。=16g6 (19) 4进一步的讨论 将本文对于AFT算法的推导方法用于一维Fourier系数的AFT算法，可得到与式(2)相 同的公式.可见，本文得到的结果是一维AFT算法在二维的自然推广.初步的数值计算结果 表明，该算法有较快的收敛速度和较高的精度，更重要的是可将该方法推广到一维及二维小 波系数的计算上，称之为AWT(Arithmetic Wavelet Transform)算法. 致谢北京大学潘承彪教授、北京科技大学容尔谦教授对该研究提出了宝贵意见，在此表示感谢！ 参考文献 1 Walker W J,Schiff J L.Convolution and the Arithmetic Fourier Transform,Its Applications. Australia:Gold Coast Australia,1992.13 15 2 Tufts D W,Sadasiv G.The Arithmetic Fourier Transform.IEEE ASSP Magaine,1988.13~17 3陈兆斗，申亚男，陈难先.整环上的M6bius函数与一个逆问题的解.科学通报，1993,38(21)：1936~ 1939 4盖尔芳特HM,希洛夫.广义函数(I).北京：科学出版社，1965.31 5陈兆斗，陈难先.M6bius反演与“算术Wavelet变换".自然科学进展，1996,6(6)：664~672

陈兆斗等 整 环上 的二 维 算法 反 演公 式得到 一 摄硼 一 摄篙赢卿 其 中 产是 上 的 函数 从几何 的观点可 以清楚地看到 采样 点集 的结构 · 平行 线族 今 一 二 ， 与 令 一 一 二 ， 分别是 等距 的平行线族 ， 两条相 邻平 行 线 间距 离 凡 二 · 线族 吞与 几是 相 互 正 交 的 ， 它 们将平 面划分 为一 系 列 正 方形 网络 ， 网格 的交 点 即 为 户 中的 点 由 的定义 可 推 出 当 声与 相 伴 时 ， 一 气 一 。 扩 又 由于相 伴元 的 函 数值相 等 ， 所 以 可 以 把级数 中对 刀的求和 限制在第一象限 内 ‘ 口 二 ， 即 七 ， 之 于 是级数 可 以 表示 为 几 。 特别 当力 ， 关于 和 分简单 一 一 。 ‘ 场 二 尹谓，‘ 一 。 菩 。各产‘ ” ，， 一 ‘，‘， 都是偶 函数 时 ， ‘ 。 。 ， 由式 ， 的计算将 会 十 一 缺 ， ，。 ‘ 一 携 ， 却 · 进一步的讨论 将本文 对于 算 法 的推 导方 法 用 于 一 维 系数 的 算 法 ， 可 得 到 与式 相 同的公 式 可 见 ， 本 文 得 到 的结果 是 一 维 算 法 在 二 维 的 自然 推 广 初 步 的数值计算结果 表 明 ， 该算法 有 较快 的 收敛速 度 和 较 高的精度 更 重要 的是 可 将 该 方 法 推广到 一 维及 二 维小 波 系数 的计算 上 ， 称 之 为 算法 ， 致谢 北京大学潘承彪教授 、 北京科技大学容尔谦教授对该研究提 出了宝贵意见 ， 在此表示 感谢 参 考 文 献 ， 户 ， 加 加 ， ， 明 ， 一 陈兆斗 ， 申亚男 ， 陈难先 整 环 上 的 函数 与一个逆 问题 的解 科学通 报 ， ， 盖尔芳特 ， 希洛夫 广义 函 数 工 北京 科学 出版社 ， 陈兆斗 ， 陈难先 反演 与 “ 算 术 变换 ” 自然科学进展 ， ， 一

·594· 北京科技大学学报 1996年No.6 Two-dimensional AFT Algorithm on Gauss Domain Chen Zhaodou)Chen Nanxian2)Ge Xijin2) 1)Department of Mathematics and Mechanics,USTB,Beijing 100083,PRC 2)Institute of Applied Physics,USTB ABSTRACT AFT algorithm for computing coefficients of Fourier series is given first based on Mobius inversion on Gauss domain.The method used in this paper is available for computing coefficients of wavelet. KEY WORDS AFT algorithm,Mobius inversion,Gauss domain,comb 6-function 3333333333383938393393333333333833333839333333839333333米 科研成果 模糊数学在工具钢碳化物评级自动化中的应用 钢中共晶碳化物分布不均匀性是反映钢材内在质量的重要指标之一，如何检验碳化物的 不均匀性，如何对其评级，是钢的生产厂家与使用单位共同关心的问题. 由于钢中碳化物分布的不均匀性，模糊性以及级别间的渐变性，使得对其定量化描述相 当困难，故时至今日国内外仍采用人工比较的方法对碳化物进行评级.这就很难保证各工厂、 各地区在评级的一致性，况且对评级的不一致性也没有不受主观因素影响的仲裁方法. 通过对合金工具钢共晶碳化物的不均匀性的研究，探寻其分布规律和影响其级别的因 素，构造了定量化描述碳化物分布规律的两种数学模型，并设计出不依赖检验人员的工作状 态等主观因素，能比较客观的评定钢中碳化物级别的自动评级系统—FCP.还利用此系 统对合金工具钢共晶碳化物的标准图谱GB1299一85随机进行了评级检验，准确率为100%. 从而可望使对碳化物的评级工作从目前的人工比较方法发展到用仪器测量、数字显示结果的 科学方法。 该成果的推广应用，可望保证对碳化物评级的一致性，对提高评级精度、快速性及材料的 利用率，实现评级自动化，不论在理论上还是实用价值上都有十分重要的意义，且有广泛的应 用前景与明显的经济效益

北 京 科 技 大 学 学 报 年 一 泛 面 ， ， ， ， ， ， ， 一 几。 卜络臼司称争组《 豁汤《 杯取念乙取净写抓韶卜翔心卜 解取争孟韶争聋阵卜争络心解韶解争璐陀取净翎叼拟解卜李绍《 拟卜 日挑争组《 卜落引熟 科研成果 模糊数学在工具钢碳化物评级 自动化 中的应用 钢 中共 晶碳 化物 分布 不 均匀 性 是 反 映钢材 内在 质量 的重 要 指 标 之 一 ， 如何 检 验碳 化 物 的 不 均匀 性 ， 如何 对其评级 ， 是 钢 的生 产厂 家与使用 单位 共 同关心 的 问题 由于 钢 中碳 化 物分布 的不 均 匀 性 ， 模 糊 性 以及 级 别 间 的渐 变性 ， 使得 对其 定 量 化 描 述 相 当困难 ， 故 时至今 日国 内外仍采 用人 工 比较 的方法 对碳 化物进 行评级 这 就很难保证各工 厂 、 各地 区在评级 的一致性 ， 况且 对评级 的不 一 致性 也 没有 不 受 主观 因素影 响 的仲裁 方 法 通 过 对合 金 工 具 钢共 晶碳 化 物 的不 均 匀 性 的研 究 ， 探 寻 其分 布 规律 和 影 响其级 别 的 因 素 ， 构 造 了定 量 化 描 述 碳 化 物分 布规律 的两 种 数学 模 型 ， 并 设 计 出不 依 赖 检 验 人 员 的工作 状 态等 主 观 因 素 ， 能 比较 客观 的 评 定 钢 中碳 化 物 级 别 的 自动 评级 系 统 － 即 还 利 用 此 系 统对合金 工具 钢共 晶碳 化 物 的标 准 图谱 一 随机进行 了评级检 验 ， 准确 率 为 从而 可望 使 对碳 化物 的评级 工作 从 目前 的人 工 比较方 法 发展 到用 仪器 测 量 、 数 字 显示 结果 的 科学方法 该成果 的推广 应 用 ， 可望 保证 对碳 化物评级 的一致 性 ， 对提 高评级精度 、 快 速性 及 材料 的 利 用率 ， 实现评 级 自动化 ， 不 论在理论 上 还是 实用 价值 上 都有 十分 重要 的意义 ， 且 有 广泛 的应 用前景 与 明显 的经 济效 益