当前位置：文档之家 › chapter 10 数据结构

chapter 10 数据结构

  • 格式：ppt
  • 大小：439.00 KB
  • 文档页数：31

下载文档原格式

  / 31

合集下载

数据结构第十章共48页PPT资料

数据结构第十章共48页PPT资料
3
.各节给出算法运行时间代价的大略估算一般都 按平均情况进行估算.对于那些受对象关键码序 列初始排列及对象个数影响较大的,需要按最好 情况和最坏情况进行估算.
.插入排序
.插入排序的基本思想每步将一个待排序的对象, 按其关键码大小,插入到前面已经排好序的一组 对象的适当位置上,直到对象全部插入为止.
Байду номын сангаас .内部排序:待排序的序列存放在计算机的内存 中进行的排序过程.
.外部排序:若待排序的记录量很大,以致内存中一 次不能容纳全部记录,在排序过程中需对外存进行 访问的排序过程.
.本章讨论内部排序,且所有关键字都是整数,待排 序的记录以顺序存储结构存储.
.排序的时间开销:排序的时间开销是衡量算法好 坏的最重要的标志.排序的时间开销可用算法执行 中的数据比较次数与数据移动次数来衡量.
21 25 49 25* 16 08
13
21 16 08 25* 25 49
i=2
012345
Gap = 2
21 16 08 25* 25 49
21 16 08 25* 25 49
08 16 21 25* 25 49
14
08 16 21 25* 25 49
i=3
012345
Gap = 1
08 16 21 25* 25 49
然后缩小间隔 gap,例如取 gap = gap/2,重复 上述的子序列划分和排序工作.
直到最后取 gap == 1,将所有对象放在同一个 序列中,排序就结束.
12
21 25 49 25* 16 08
i=1
012345
Gap = 3
21 25 49 25* 16 08
21 25 49 25* 16 08

数据结构答案 第10章 排序学习与指导

数据结构答案 第10章 排序学习与指导

第10章排序10.1 知识点分析1．排序基本概念：（1）排序将数据元素的任意序列，重新排列成一个按关键字有序（递增或递减）的序列的过程称为排序。

（2）排序方法的稳定和不稳定若对任意的数据元素序列，使用某个排序方法，对它按关键字进行排序，若对原先具有相同键值元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的；反之，则称为不稳定的。

（3）内排序整个排序过程都在内存进行的排序称为内排序，本书仅讨论内排序。

（4）外排序待排序的数据元素量大，以致内存一次不能容纳全部记录，在排序过程中需要对外存进行访问的排序称为外排序。

2．直接插入排序直接插入排序法是将一个记录插到已排序好的有序表中，从而得到一个新的，记录数增1的有序表。

3．二分插入排序二分插入排序法是用二分查找法在有序表中找到正确的插入位置，然后移动记录，空出插入位置，再进行插入的排序方法。

4．希尔排序希尔排序的基本思想是：先选取一个小于n的整数d1作为第一个增量，把待排序的数据分成d1个组，所有距离为d1的倍数的记录放在同一个组内，在各组内进行直接插入排序，每一趟排序会使数据更接近于有序。

然后，取第二个增量d2，d2< d1，重复进行上述分组和排序，直至所取的增量d i=1（其中d i< d i-1 < ……< d2< d1），即所有记录在同一组进行直接插入排序后为止。

5．冒泡排序冒泡法是指每相邻两个记录关键字比大小，大的记录往下沉（也可以小的往上浮）。

每一遍把最后一个下沉的位置记下，下一遍只需检查比较到此为止；到所有记录都不发生下沉时，整个过程结束。

6．快速排序快速排序法是通过一趟排序，将待排序的记录组分割成独立的两部分，其中前一部分记录的关键字均比枢轴记录的关键字小；后一部分记录的关键字均比枢轴记录的关键字大，枢轴记录得到了它在整个序列中的最终位置并被存放好。

第二趟再分别对分割成两部分子序列，再进行快速排序，这两部分子序列中的枢轴记录也得到了最终在序列中的位置而被存放好，并且它们又分别分割出独立的两个子序列……。

数据结构第九、十章作业答案

数据结构第九、十章作业答案

数据结构第九、⼗章作业答案第九章查找⼀、填空题1. 在数据的存放⽆规律⽽⾔的线性表中进⾏检索的最佳⽅法是顺序查找（线性查找）。

2. 线性有序表（a 1，a 2，a 3，…，a 256)是从⼩到⼤排列的，对⼀个给定的值k ，⽤⼆分法检索表中与k 相等的元素，在查找不成功的情况下，最多需要检索 8 次。

设有100个结点，⽤⼆分法查找时，最⼤⽐较次数是 7 。

3. 假设在有序线性表a[1..20]上进⾏折半查找，则⽐较⼀次查找成功的结点数为1；⽐较两次查找成功的结点数为 2 ；⽐较四次查找成功的结点数为 8 ,其下标从⼩到⼤依次是1,3,6,8,11,13,16,19______，平均查找长度为 3.7 。

解：显然，平均查找长度＝O （log 2n ）<5次（25）。

但具体是多少次，则不应当按照公式)1(log 12++=n n n ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。

因为这是在假设n ＝2m -1的情况下推导出来的公式。

应当⽤穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=3.74．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 ⽐较⼤⼩。

5. 在各种查找⽅法中，平均查找长度与结点个数n ⽆关的查找⽅法是散列查找。

6. 散列法存储的基本思想是由关键字的值决定数据的存储地址。

7. 有⼀个表长为m 的散列表，初始状态为空，现将n （n8、设⼀哈希表表长M 为100 ，⽤除留余数法构造哈希函数，即H （K ）=K MOD P （P<=M ）, 为使函数具有较好性能，P 应选（ 97 ）9、在各种查找⽅法中，平均查找长度与结点个数⽆关的是哈希查找法10、对线性表进⾏⼆分查找时，要求线性表必须以顺序⽅式存储，且结点按关键字有序排列。

数据结构第10章

数据结构第10章

蔡之华主讲
6 24
第一次排序:
{5
7
64}
89
6
24
第二次排序:
{5
7
89
6
24
第三次排序:
{5
7
64
89}
6
24
第四次排序:
ቤተ መጻሕፍቲ ባይዱ{5
6
7
64
89}
24
第五次排序:
{5
6
7
24
64
89}
直接插入排序过程
计算机学院 蔡之华主讲 2.希尔(shell)排序(又称缩小增量排序)
(1)基本思想：把整个待排序的数据元素分成若干个小组，对同
计算机学院
蔡之华主讲
第10章 排序
主 要 知 识 点
排序的基本概念 插入排序 选择排序 交换排序归并排序 基数排序 性能比较
计算机学院
蔡之华主讲
10.1 排序的基本概念
排序是对数据元素序列建立某种有序排列的过程,是把一个数 据元素序列整理成按关键字递增（或递减）排列的过程。 关键字是要排序的数据元素集合中的一个域，排序是以关键字 为基准进行的。 主关键字:数据元素值不同时该关键字的值也一定不同，是能 够惟一区分各个不同数据元素的关键字;不满足主关键字定义 的关键字称为次关键字。 内部排序是把待排数据元素全部调入内存中进行的排序。 外部排序是因数量太大，把数据元素分批导入内存，排好序后 再分批导出到磁盘和磁带外存介质上的排序方法。
for(m = 0; m < numOfD; m++) //共numOfD次循环 { span = d[m]; //取本次的增量值 for(k = 0; k < span; k++) //共span个小组 { //组内是直接插入排序，区别是每次不是增1而是增span for(i = k; i < n-span; i = i+span) { temp = a[i+span]; j = i; while(j > -1 && temp.key <= a[j].key) { a[j+span] = a[j]; j = j-span; } a[j+span] = temp; } } } }

数据结构第10章 习题答案

数据结构第10章 习题答案

1．下列排序算法中，其中（ D ）是稳定的。

A. 堆排序，冒泡排序B. 快速排序，堆排序C. 直接选择排序，归并排序D. 归并排序，冒泡排序2．有一组数据（15，9，7，8，20，-1，7，4）用快速排序的划分方法进行一趟划分后数据的排序为 ( A )（按递增序）。

A．下面的B，C，D都不对。

B．9，7，8，4，-1，7，15，20C．20，15，8，9，7，-1，4，7 D. 9，4，7，8，7，-1，15，203.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（ B ）。

A. 直接插入排序B. 快速排序C. 直接选择排序D. 堆排序4．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ D ）方法最快。

A．起泡排序 B．快速排列 C．Shell排序 D．堆排序 E．简单选择排序5．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( A )排序法。

A. 插入B. 选择C. 希尔D. 二路归并6. 在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是（ A ）。

A. 选择B. 冒泡C. 插入D. 堆7. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（ C ）次比较。

A. 3B. 10C. 15D. 258. 对序列{15，9，7，8，20，-1，4，} 用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是 ( B )A. lB. 4C. 3D. 29. 堆排序是（ E ）类排序A. 插入B. 交换C. 归并D. 基数E. 选择10．排序方法有许多种，（1）法从未排序的序列中依次取出元素，与已排序序列（初始时为空）中的元素作比较，将其放入已排序序列的正确位置上；（2）法从未排序的序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端；交换排序方法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换；（3）和（4）是基于这类方法的两种排序方法，而（4）是比（3）效率更高的方法；（5）法是基于选择排序的一种排序方法，是完全二叉树结构的一个重要应用。

数据结构 chapter10

数据结构 chapter10

Department of Computer Science & Technology, Nanjing University
fall
DATA STRUCTURES
多级索引结构形成 m 路搜索树
Department of Computer Science & Technology, Nanjing University
第10章 文件组织、索引结构
文件组织 动态索引结构
Department of Computer Science & Technology, Nanjing University Data Structure
fall
10.1 文件组织
DATA STRUCTURES
文件的基本概念
什么是文件 文件是存储在外存上的数据结构。 文件分操作系统文件和数据库文件
是指向子树的指针，0 i n < m；Ki 是关键码， 1 i n < m。 Ki < Ki+1, 1 i < n。
▪ 在子树 Pi 中所有的关键码都小于 Ki+1，且大于 Ki， 0 < i < n。
▪ 在子树 Pn 中所有的关键码都大于Kn； ▪ 在子树 P0 中的所有关键码都小于 K1。 ▪ 子树 Pi 也是 m 路搜索树，0 i n。
Department of Computer Science & Technology, Nanjing University
fall
DATA STRUCTURES
索引表用于指示逻辑记录与物理记录间的对应关 系，它是按关键码有序的表。
索引顺序文件：主文件也按关键码有序。此时 可对主文件分组，一组记录对应一个索引项。 称这种索引表为稀疏索引。

数据结构第九、十章 作业答案

第九章 查找一、填空题1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。

2. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值k ，用二分法检索表中与k 相等的元素，在查找不成功的情况下，最多需要检索 8 次。

设有100个结点，用二分法查找时，最大比较次数是 7 。

3. 假设在有序线性表a[1..20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ,其下标从小到大依次是1,3,6,8,11,13,16,19______，平均查找长度为 3.7 。

解：显然，平均查找长度＝O （log 2n ）<5次（25）。

但具体是多少次，则不应当按照公式)1(log 12++=n n n ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。

因为这是在假设n ＝2m -1的情况下推导出来的公式。

应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=3.7 ！！！4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。

5. 在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是 散列查找 。

6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。

7. 有一个表长为m 的散列表，初始状态为空，现将n （n<m ）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。

如果这n 个关键码的散列地址都相同，则探测的总次数是 n(n-1)/2=（ 1＋2＋…＋n-1） 。

(而任一元素查找次数 ≤n-1)8、设一哈希表表长M 为100 ，用除留余数法构造哈希函数，即H （K ）=K MOD P （P<=M ）, 为使函数具有较好性能，P 应选（ 97 ）9、在各种查找方法中，平均查找长度与结点个数无关的是哈希查找法10、对线性表进行二分查找时，要求线性表必须以 顺序 方式存储，且结点按关键字有序排列。

数据结构Ch10习题答案

第十章内部排序一、择题1．用直接插入排序法对下面四个表进行（由小到大）排序，比较次数最少的是（B）。

A．（94，32，40，90，80，46，21，69）插32，比2次插40，比2次插90，比2次插80，比3次插46，比4次插21，比7次插69，比4次B．（21，32，46，40，80，69，90，94）插32，比1次插46，比1次插40，比2次插80，比1次插69，比2次插90，比1次插94，比1次C．（32，40，21，46，69，94，90，80）插40，比1次插21，比3次插46，比1次插69，比1次插94，比1次插90，比2次插80，比3次D．（90，69，80，46，21，32，94，40）插69，比2次插80，比2次插46，比4次插21，比5次插32，比5次插94，比1次插40，比6次2．下列排序方法中，哪一个是稳定的排序方法（BD）。

A．希尔排序B．直接选择排序C．堆排序D．冒泡排序下列3题基于如下代码：for(i=2;i<=n;i++){ x=A[i];j=i-1;while(j>0&&A[j]>x){ A[j+1]=A[j];j--;}A[j+1]=x}3．这一段代码所描述的排序方法称作（A）。

A．插入排序B．冒泡排序C．选择排序D．快速排序4．这一段代码所描述的排序方法的平均执行时间为（D）A．O(log2n) B．O(n) C．O(nlog2n) D．O(n2)5．假设这段代码开始执行时，数组A中的元素已经按值的递增次序排好了序，则这段代码的执行时间为（B）。

A．O(log2n) B．O(n) C．O(nlog2n) D．O(n2)6．在快速排序过程中，每次被划分的表（或了表）分成左、右两个子表，考虑这两个子表，下列结论一定正确是（B）。

A．左、右两个子表都已各自排好序B．左边子表中的元素都不大于右边子表中的元素C．左边子表的长度小于右边子表的长度D．左、右两个子表中元素的平均值相等7．对n个记录进行堆排序，最坏情况下的执行时间为（C）。

数据结构第十章

（1） 顺序排序 —— 排序时直接移动记录； （2）链表排序 —— 排序时只移动指针； （3）地址排序 —— 排序时先移动地址，最后再移动记录。 注：地址排序中可以增设一维数组来专门存放记录的地址。
8
注：大多数排序算法都是针对顺序表结构的(便于直接移动元素)
# define MAXSIZE 20 //设记录不超过20个 typedef int KeyType ; //设关键字为整型量（int型）
优点：每趟结束时，不仅能挤出一个最大值到最后面位置， 还能同时部分理顺其他元素；一旦下趟没有交换发 生，还可以提前结束排序。
前提：顺序存储结构
例：关键字序列 T=(21，25，49，25*，16，08），请写出 冒泡排序的具体实现过程。
初态： 21，25，49， 25*，16， 08 第1趟 21，25，25*，16， 08 ， 49 第2趟 21，25， 16， 08 ，25*，49 第3趟 21，16， 08 ，25， 25*，49 第4趟 16，08 ，21， 25， 25*，49 第5趟 08，16， 21， 25， 25*，49
优点：因为每趟可以确定不止一个元素的位置，而且呈指数增 加，所以特别快！
前提：顺序存储结构
27
具体过程
❖ 一趟快速排序采用从两头向中间扫描的办法。 ❖ 假设原始数据已存于一个一维数组r中，具体的做法是： 设两个指示器i和j，初始时i指向数组中的第一个数据，j指 向最末一个数据。i先不动使j逐步前移，每次对二者所指的 数据进行比较，当遇到r[i]大于r[ j]的情况时，就将二者对调 位置；然后令j固定使i逐步后移做数据比较，当遇到r[i]大于 r[j] 时，又进行位置对调；然后又是i不动使j前移作数据比 较；……； ❖ 如此反复进行，直至i与j两者相遇为止。

数据结构课件 第10章

数 据 结 构 第10章 内部排序10.1 概述•什么是排序？–排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。

–若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。

10.1 概述•待排序的数据类型#define MAXSIZE 1000 // 待排顺序表最大长度typedef int KeyType; // 关键字类型为整数类型typedef struct { KeyType key; // 关键字项 InfoType otherinfo; // 其它数据项} RcdType; //记录类型typedef struct { RcdType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元 int length; // 顺序表长度} SqList; // 顺序表类型#define MAXSIZE 1000 // 待排顺序表最大长度typedef int KeyType; // 关键字类型为整数类型typedef struct { KeyType key; // 关键字项 InfoType otherinfo; // 其它数据项} RcdType; //记录类型typedef struct { RcdType r[MAXSIZE+1]; // r[0]闲置或用作哨兵单元 int length; // 顺序表长度} SqList; // 顺序表类型10.1 概述•内部排序的类别–插入类：将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度。

–交换类：通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。

–选择类：从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度。

–归并类：通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

∞
Discrete model for channel with ISI
The noise is zero mean Gaussian distributed with auto correlation function
N 0 xk − j 1 * E ( kν j ) = ν 2 0
∫
∞
−∞
h* (t − nT )h(t − mT )dt
Denote the receiver output is
yn ≡ y (nT ) ≡ ∫ rl (t )h* (t − nT )dt
−∞
∞
* * CM (I p ) = 2 Re ∑ I n yn − ∑∑ I n I m xn −m n n m
C (z ) F (z )F * (z −1 ) + N 0 = F * (z −1 )
* −1
2 2
Infinite length equalizer
ˆ Ik =
j = −∞
∑c v
∞
j k− j
Using the principle of orthogonality
E (ε v
* k k −l
) = 0,
−∞<l <∞
* ∑ c j vk − j vk − l = 0 j = −∞
π T
∫π
−
π T
T
dω X (exp( jωT ))
−1
The SNR becomes
TN 0 γ∞ = 2 = σ n 2π 1
∫π
−
π T
T
dω X (exp( jωT ))
or
T 2 N 0 γ∞ = 2π
∫π
−
π T
T
2 H (ω + 2πn T ) dω
or
C (z ) = 1 / F (z )
Taking into account of the noise whitening filter
1 1 C ' (z ) = = * −1 F (z )F z X (z )
( )
C (z ) = 1 / F (z )
1 1 C ' (z ) = = * −1 F (z )F z X (z )
vk = ∑ f n I k − n + η k
n =0
L
{ηk} is the AWGN {fk} is the tap coefficients Z-1 fL-1 + × Z-1 fL ×
{Ik} f0 ×
Z-1 f1 ×
Z-1
Z-1=delay of T
+ {η k }
{vk}
example
∞
Substitute the εk
E I k −
* k − j k −l
or
j = −∞
∑ c E (v
∞ j
v
) = E (I v ),
* k k −l
−∞<∞
Since
vk = ∑ f n I k − n + η k
n =0
L
then
E (v
* k − j k −l
γ ∞ = 1 N0
10-2-2 Mean Square Error (MSE) Criterion The tap weight are adjusted to minimize the mean square value of error
ˆ εk = In − Ik
ˆ J = E εk = E Ik − Ik
n =0
,
k = 0,1,2,... L
Using the viterbi algorithm Assume the interference takes place between L+1 symbols The state at any time instant k is
Sk = (I k −1 , I k −2 ,... I k − L )
(otherwise)
( k − j ≤ L)
x (z ) =
k =− L
∑x z
k
L
−k
X (z ) = F (z )F (z
*
−1
)
Passing sequence yk through the digital filter 1/F*(z-1) results in the output sequence vk
This chapter deal with the receiver design when the channel presents the unknown distortion and AWGN Channel distortion Intersymbol interference (ISI)
ˆ I k = q0 I k + ∑ I n q k − n +
n≠k
j = −∞
∑c η
j
∞
k− j
The peak distortion is
D(c ) =
n = −∞ n≠0
∑q
∞
n
=∑
∞
n = −∞ j = −∞ n≠0
∑c
∞
j
f n− j
Dc is the function of tap weights
v
)= ∑ f
L n=0
* n n+l − j
f
+ N 0δ lj
xl − j + N 0δ lj ( l − j ≤ 0 ) = otherwise 0
f −*l * E (I k vk − l ) = 0
and
(− L ≤ l ≤ 0)
otherwise
The z transform is
{vk} c-K ×
Z-1 cK+1 ×
Z-1
Z1
Z-1 × cK ×
cK-1
+
Tap gain adjustment Complexity: linear function of the tap length
K
{Ik}
ˆ Ik =
j=− K
∑c v
j k− j
Peak distortion criterion
rl (t ) = lim ∑ rk f k (t )
N →∞ k =1
N
fk(t) is the complete orthogonal function
rk (t ) = ∑ I n hkn + z k
n
hk is the projection of h(t) onto fk(t)
1 * E z k z m = N 0δ km 2
The ISI free can be obtained when if D(c) =0, i.e.
qn =
j = −∞
∑c
∞
j
f n− j
1, (n = 0) = 0, (n ≠ 0)
Using the representation of the Z transform
Q ( z ) = C ( z )F ( z ) = 1
To compensate or reduce ISI -> Using equalizer Based on maximum-likelihood Equalizer Linear filter with adjustable coefficients Decision feedback
Optimum likelihood receiver Assume the received signal can be expressed as
Substitute the rl expression into above equation and denotes
xn = ∫ h (t )h (t + nT )dt
* −∞
∞
then
y k = ∑ I n xk − n + vk
n
vk = ∫ z (t )h (t − kT )dt
* −∞
rk = ∑ I n hkn + z k ,
n
k = 1,2,...
Where In is the information data and hk is the equivalent channel response, zk is the AWGN signal.
Optimum maximum-likelihood receiver Received signals
PM 1 (I L+1 ) = max ∑ ln p (vk I k , I k −1 ,... I k − L )
I1 k =1
L +1
example
v1 = I1 + η1 v2 = I 2 + I 1 + η 2
PM 1 (I 2 , I1 ) = − ∑ vk − ∑ I k − j , k =1 j =0
qn =
j = −∞
c j f n − j cj:impulse response of equalizer ∑
∞
fn: impulse response of the cascade linear filter
At the kth sampling instance it is expressed as
( )
Performance of the infinite tap equalizer : expressed as SNR at the output The power spectrum density of the noise sequence