积性函数系列(一):欧拉函数

November 14, 2014 at 1:23 am

本系列是数论篇章的第一篇(于是又挖了一个数论的坑orz),主要介绍、证明初等数论中一些重要的概念、结论。 在微积分学领域,积性函数指的是具有的函数,在数论领域这个概念略有不同,仅定义在正整数上,它揭示了整数的很多性质。废话不多说,直奔主题。 为了区分通常意义上的函数,我们定义算数函数: 定义1.1 定义在所有正整数上的函数称为算数函数。 在整个积性函数篇里,不加说明地,我们总是讨论算数函数。 定义1.2 算术函数如果满足对于任意两个互质的正整数和,均有,就称为积性函数(或乘性函数)。如果对于任意两个正整数和,均有,就称为完全积性函数。 很容易找到一些trivial的积性函数,如,事实上所有的幂函数都是积性函数。 结合积性函数的定义和算数基本定理,很容易得到下面的定理: 定理1.1 如果是一个积性函数,对于任意的正整数有素数幂分解,那么有 证明:略,使用数学归纳法即可。 好了,介绍完了积性函数的基本概念,就开始介绍今天的主角,欧拉函数,它也被称为欧拉函数。顾名思义,它是由欧拉首先研究的。 定义1.3 欧拉函数定义为不超过且和互质的正整数的个数。 下面我们就来探讨欧拉函数在各个点上的取值。很容易得到对于素数,,那么反过来是不是也成立呢? 定理1.2 如果是素数,那么.反之,如果是正整数且满足,那么是一个素数。 证明:前句可由互质定义得到,我们只证明后句。若不是素数,那么或是1或是合数。而,但若是合数,得有因子,而不与自身互质,这使得和互质的数至多只有个,所以也不可能,故是素数。 […]

基础链路层协议(三):考虑噪音的停止-等待型单向协议

November 12, 2014 at 11:04 am

延续上一节的内容,这一节我们考虑更现实的情况,传输的过程中存在噪音。这意味着传输的过程可能存在错误,可能丢失数据,我们的协议需要适应这种情况。 为了使讨论简单,我们假设接收方总能通过校验和识别出错误的帧。如果不凑巧错误的帧和正确的包校验和一致,协议就挂了。幸运的是这通常情况下不会发生。(关于计算各类校验和的方法过几天再挖一个坑把) 由于接收方只有在收到帧后才会发送应答帧,所以一个简单的想法就是在原协议的基础上加上一个定时器,如果发送方一直没有接收到应答帧,超时后就将帧重传。但这里有一个陷阱。如果接收方确实收到帧了,也确实发送了应答帧了,但不幸的是应答帧彻底丢了,而发送方却不知道,所以就会将之前的帧重新发送,接收方就可能接收到冗余的数据。为了解决这个问题,我们需要使用sequence number[序号]来记录帧的编号,这样当接收方接收到正确序号的帧时才会将数据传递给网络层。核心的设计就是序号的位数。 考虑我们发送方由于超时,重传了编号为m的帧,那么实际上第m-1个帧已经正确地被接收方接收且发回了应答,否则发送方此时应发编号为m-1的帧;如果接收方确实没有接收到数据,那么发送方重发m是正确的,接收方接收到后正常处理即可。如果是应答帧丢失,那么实际上接收方需要的是编号为m+1的帧。所以实际上如果发送方发送编号为m的帧,那么接收方要么确实需要m,要么需要的是m+1,因此sequence number只要一个比特位就够了。 基于上述讨论,对协议进行修改,注意此时事件的种类变成了三种:帧到达、校验错误和超时: typdef enum{frame_arrival, cksum_err, timeout} event_type; 我们在帧结构中加入sequence number和应答对应编号用的acknowledge: typedef struct{ packet info; seq_nr seq; […]

基础链路层协议(二):停止-等待型单向协议

November 8, 2014 at 11:33 am

延续上一节的内容,在这一节中,我们移除假设3,即B不能总是无限快地处理接收到的数据。这在实际通信中是非常普遍的,数据发送方可能是一个非常高端的机器,而接收方可能只是普通的家用电脑。接收方B性能不足以瞬间处理A发送的所有数据。 一个比较通用的方式是发送方不再不断地发送数据,而是在发送一个数据后,停止发送并等待接收方的响应,即所谓的stop-and-wait策略。当接收方B处理完数据后(将数据交由网络层后),向发送方A发送一个任意的帧,发送方在接收到帧后再发送下一个包。这种策略是一个流控制协议的简单例子。 实现上非常简单,我们只需要在发送方上加上和接收方类似的事件等待过程: void sender2(void){ frame s; packet buffer; event_type event; while (true) { from_network_layer(&buffer); s.info = buffer; to_physical_layer(&s); wait_for_event(&event); […]

基础链路层协议(一):乌托邦单向协议

November 6, 2014 at 12:47 am

最近正在对计算机网络的基础知识进行复习,由于链路层的一些基础协议在高层协议中也有所体现,于是开始挖链路层基础协议的坑。定位为比较入门级别的复习。 为了使接下来的讨论简单一些,我们对网络模型进行一定的简化: 我们假设各个层之间,如物理层、数据链路层、网络层之间,相互独立,层与层之间只能通过信息的传递形成交互。 上述简化针对于本系列的所有内容。 那么问题来了。我们希望建立一个由A向B传输数据的协议,从而实现A和B的数据传输。本篇介绍最为简单的一种协议,在本篇中,我们假设: 1.只进行A向B的单向传输 2.A总是可以不断产生数据 3.B总是可以立即处理收到的数据 4.数据不会发生丢失 5.忽略传输的时间 6.机器不会损坏 基于上述假设,对于发送端而言,实际上只需要不断地从网络层获取数据,然后发送给物理层就可以了。下面的代码给出了一个典型的发送端: void sender1(void){ frame s; packet buffer; while (true) […]