Category Archives: 计算理论

视频编码与封装综述

随着多媒体技术和网络通信技术的快速发展,视频多媒体应用已经覆盖了大众生活的方方面面。尤其是近年来高清和超高清视频应用越来越广泛,相比于标清视频,高清视频分辨率更高、画面更清晰,其数据量也更大。如果未经压缩,这些视频将很难应用于实际的存储和传输。这里我们就要提到视频应用中的一项关键技术——视频压缩编码技术

 

视频压缩编码技术可以有效地去除视频数据中冗余信息,实现视频数据在互联网中快速传输和离线存储

视频技术起源于第二次工业革命,随着视频技术的发展,一系列的视频编码标准被研发被使用。

压缩标准的变迁
目前已有的视频压缩标准有很多种,包括国际标准化组织(International Organization for Standardization, ISO)/国际电工技术委员会(International Electrotechnical Commission, IEC)制定的MPEG-1、MPEG-2、MPEG-4标准,国际电信联盟电信标准化部门(International Telecommunication Union-Telecom, ITU-T)制定的H.261、H.263。 

2003年3月,ITU-T和ISO/IEC 正式公布了H.264/MPEG-4 AVC视频压缩标准。H.264作为目前应用最为广泛的视频编码标准,在提高编码效率和灵活性方面取得了巨大成功,使得数字视频有效地应用在各种各样的网络类型和工程领域。为了在关键技术上不受国外牵制,同时也不用交大量的专利费用,中国也制定了AVS系列标准,可以提供与H.264/AVC相当的编码效率。

 

随着用户体验的升级,更高码率的视频也在被提供,比如超高清(3840 x 2160)。相对于标清视频,其分辨率更高,数据量也更多。在存储空间和网络带宽有限的情况下,现有的视频压缩技术已经不能满足现实的应用需求。为了解决高清及超高清视频急剧增长的数据率给网络传输和数据存储带来的冲击ITU-T和ISO/IEC联合制定了具有更高的压缩效率的新一代视频压缩标准HEVC(High Efficiency Video Coding)

HEVC简单介绍
HEVC:新一代视频压缩标准,以传统的混合视频编码为框架,并采用了更多的技术创新,包括灵活的块划分方式、更精细的帧内预测、新加入的Merge模式、Tile划分、自适应样点补偿等。 

这些技术一方面使得HEVC编码性能比H.264/AVC提高了一倍,另一方面也将编码复杂度大大增加,不利于HEVC的应用和推广

 

在这里着重说一下块划分方式——对编码性能提升最大。块划分包括编码单元(CU)、预测单元(PU)和变换单元(TU)。但是,递归的对每个编码单元进行率失真优化过程(RDO)来选择最优的模块划分的复杂度很高,其需要巨大的计算复杂度。因此降低HEVC编码复杂度的是视频行业人员所希望看到的。

640
图1 视频编码框图
新一代编码器对比
641
常见的封装格式有以下几种:· AVI(Audio Video Interleave):只能封装一条视频轨和音频轨,不能封装文字,没有任何控制功能,因而也就无法实现流媒体,其文件扩展名是.avi。

· WMV(Windows Media Video):具有数字版权保护功能,其文件扩展名是.wmv/.asf。

· MPEG(Moving Picture Experts Group):可以支持多个视频、音轨、字幕等,控制功能丰富,其文件扩展名是.mp4。

· Matroxska:提供非常好的交互功能,比MPEG更强大,其文件扩展名是.mkv。

· QuickTime File Farmat:由Apple开发,可存储内容丰富,支持视频、音频、图片、文字等,其文件扩展名是.mov。

· FLV(Flash Video):由Adobe Flash延伸而来的一种视频技术,主要用于网站。

· TS流(Transport Stream):传输流,将具有共同时间基准或独立时间基准的一个或多个PES组合(复合)而成的单一数据流(用于数据传输)。目前TS流广泛应用于广播电视中,如机顶盒等。

总结
本文简单介绍了视频的编码与封装,其是视频通信中重要的一步,如果这一步出了问题,很容易导致视频无法被读取或无法播放的状态。下一节,我们将来说一下视频通信中的音视频处理技术。from:https://mp.weixin.qq.com/s/9hClcofo8HEI8QqDpef12Q

一分钟理解TCP重传

为什么需要重传

任何信息在介质中传输可能丢失,这是由于传输介质的物理特性决定的,所以网络不可能被设计为“可靠的”(不是由于考虑“性能”原因而是压根做不到)。既然物理层无法提供可靠数据传输那么只能由协议提供可靠传输了,其中最有名的协议就是TCP了。

TCP是基于IP的网络协议,它提供可靠、有序的数据传输。在数据传输之前客户端和服务器端通过三次握手建立连接,建立连接的就是双方交换Seq(数据包序号)、MSS(每个TCP数据包大小) 、Win(滑动窗口,一次可以确认多少个TCP数据包),连接建立完成后每个TCP数据包都要被ACK(确认)。简单来说TCP通过确认/重传机制实现了“数据包可靠传输”。

重传原理

TCP数据包头部包含了两个字段——Seq表示数据包序号,ACK表示确认序号。下面演示了三次握手过程中Seq和ACK的变化过程。

640

客户端随机取一个值x作为Seq发送到服务器端;服务器端回复一个TCP数据包,头部包含Seq(随机值y),ACK=x+1。注意这里有一个常见的误区,ack确认的是当前数据包的“下一个”数据包,ack其实可以作为“期望得到的下一个seq”。客户端收到服务器端回复之后单独回复一个ack=y+1,就完成TCP的握手了。

后续数据包传递都会延续seq和ack的值,如果发送端某个数据包丢失了那么接收端不会发送ack(其实是duplicate ack),发送端在等待一段时间后发现没有ack,于是主动重发数据包。发送端的等待的时间叫RTO(Retransmission TimeOut)。

RTO的选择很重要,如果太大那么网络带宽利用率会特别低,发送端要过很久才知道要重传而此时要重传的数据是在太多严重浪费带宽资源。如果太小在高延时的网络高带宽(恩,你访问国外网站就属于这种网络)中也会浪费带宽资源。于是就有了Fast Retransmit机制,简单来说当发送端发现来自接收端的多个重复ACK(duplicate ack)的时候就不再等待RTO而是直接选择重发。

总结一下:经典TCP重发是发送端主动重发的,当数据包经历了一段时间后还没有被接收端确认此时发送端主动重发数据包。Fast Retransmit是由接收端主动要求重发的,当接收端收到了“不想要”的数据包时会重复ACK“上一个”数据包从而触发发送端的重发。这两种重发策略一般是同时使用,它们是互补的。

举个例子:发送端有D1(1-10)、D2(11-20)、D3(21-30)、D4(31-40)四个数据包要发送,每个数据包10bytes用括号内的数字表示。

  • 乱序的情况:接收端收到D1,发送ack=11(D2的序号)。如果在发送过程中D4在D1之后达由于D4携带的seq=31所以接收端会丢弃这个数据包然后再次发送ack=11。此时发送端会收到两个ack(duplicate ack)如果开启了Fast Retransmit特性那么发送端立即从D2开始重新发送。
  • 丢包的情况:接收端收到D1,发送ack=11(D2的序号)。如果在发送过程中D2丢失那么后续到达的包是D3,由于D3携带的seq=21所以接收端会丢弃这个数据包然后再次发送ack=11。此时发送端也会出现duplicate ack从而触发重传。

如果接收端的ACK数据包丢失了或者网络时延太高那么也会触发重传。因为发送端对每个数据包都设置了一个RTO,如果到时间没有收到ACK它会“主动”重发数据包。

Q&A

Q:多线程对一个Socket写入是否会触发TCP重发?程序上是否要考虑“乱序”?

A:首先要搞清楚一点,我们往Socket写入的数据是“应用层数据包”而不是TCP数据包。TCP/IP协议栈会把应用层数据包划分出多个TCP数据包发送出去,每次write都会生成N个连续的TCP数据包。所以即便我们多线程往Socket写入也不会出现TCP数据包的乱序(应用层数据包可能是乱序的)。

Q:重传和拥塞控制有什么关系?

A:TCP拥塞控制是指尽可能的利用带宽,它围绕4个核心概念展开:慢启动、拥塞避免和快速重传、快速恢复。其中快速重传、快速恢复属于TCP重传机制,慢启动是指对滑动窗口的控制,拥塞避免好重传机制有一定关系,如果存在大量重传那么网络上可能出现了拥塞(拥塞避免的关键是识别拥塞)。

Q:怎么看“替代TCP”的说法?

A:TCP最遭人诟病的就是它的重传机制不可控。如果网络延时比较高或者质量比较差有一定丢包(特别是移动网络),TCP的重传机制触发“不及时”这就导致应用体验很差。比如一个1000帧的视频丢了第100帧那么后续的900帧都要重传(即便已经收到了)。当然这只是一个例子,视频还是可以做一定“弥补”的),如果是手机游戏(比如王者荣耀、荒野行动)情况就没有这么乐观了。为了尽可能的让“重传”可控于是诞生了各种“替代TCP”的自制协议(大部分是基于UDP),比如Google的QUIC、kcp。我个人对这方面研究不多,总体而言它们牺牲了TCP的一些“通用特性”来换取一定的“灵活性”,所以并不是惊天地泣鬼神的“替代TCP”。

Q:怎么看TCP单边加速

A:TCP单边加速是指针对通讯的某一端做性能加速,市面上有很多这种产品。但是个人觉得这些都是骗人的,并没有一种算法适合所有网络情况。要根据不同的网络情况配置不同的拥塞控制算法。比如“国际链路”属于高延时高带宽,配置了Google的BBR算法“梯子”的速度至少能提高70-80%(你懂得)。

from:https://mp.weixin.qq.com/s?__biz=MzIxMjAzMDA1MQ==&mid=2648945945&idx=1&sn=f92e903929975e05978ba57be64ba2bc&chksm=8f5b5215b82cdb03c3f6f57ff63ee3f24bc1029dd147b7524d44baa36a10be65c24f6067adec#rd

IPC(Inter-process communication)进程间通讯

进程间通讯方式

Method Short Description Provided by (operating systems or other environments)
File A record stored on disk, or a record synthesized on demand by a file server, which can be accessed by multiple processes. Most operating systems
Signal; also Asynchronous System Trap A system message sent from one process to another, not usually used to transfer data but instead used to remotely command the partnered process. Most operating systems
Socket A data stream sent over a network interface, either to a different process on the same computer or to another computer on the network. Typically byte-oriented, sockets rarely preserve message boundaries. Data written through a socket requires formatting to preserve message boundaries. Most operating systems
Message queue A data stream similar to a socket, but which usually preserves message boundaries. Typically implemented by the operating system, they allow multiple processes to read and write to the message queue without being directly connected to each other. Most operating systems
Pipe A unidirectional data channel. Data written to the write end of the pipe is buffered by the operating system until it is read from the read end of the pipe. Two-way data streams between processes can be achieved by creating two pipes utilizing standard input and output. All POSIX systems, Windows
Named pipe A pipe implemented through a file on the file system instead of standard input and output. Multiple processes can read and write to the file as a buffer for IPC data. All POSIX systems, Windows, AmigaOS 2.0+
Semaphore A simple structure that synchronizes multiple processes acting on shared resources. All POSIX systems, Windows, AmigaOS
Shared memory Multiple processes are given access to the same block of memory which creates a shared buffer for the processes to communicate with each other. All POSIX systems, Windows
Message passing Allows multiple programs to communicate using message queues and/or non-OS managed channels, commonly used in concurrency models. Used in RPC, RMI, and MPI paradigms, Java RMI, CORBA, DDS, MSMQ, MailSlots, QNX, others
Memory-mapped file A file mapped to RAM and can be modified by changing memory addresses directly instead of outputting to a stream. This shares the same benefits as a standard file. All POSIX systems, Windows

The following are messaging and information systems that utilize IPC mechanisms, but don’t implement IPC themselves:

Interprocess communication for Windows in C#

refer:Inter-process communication

 

简述百年计算机科学

计算机科学和数学的论文读起来向来很具有挑战性,但读完后收获也不小。我也并不总能够完全理解论文中的每一个批注,有时都无法完全明白作者的结论,但阅读它们仍然大大地开阔了我的眼界。

我是比较晚才开始意识到阅读学术论文的重要性的。当还是学生的时候,我记得我只读过两篇论文,其中一篇下面我会提到。作为程序员,我并没有很强的计算机理论背景。学术论文对我来说非常生涩和遥远。因而,我花了很长时间才意识到没有阅读这些论文对我的损失有多大。

我有些同事知道了我最近对学术论文有所研究后,都在问我建议他们从哪里开始。看了Michaels FeathersFogus做的一张类似的清单后,我也编辑了一份自认为代表了过去100年计算机科学发展历程的清单。在编辑的时候,我采用了如下的选择标准:

  • 这篇论文必须改变了世界
  • 这篇论文必须颠覆了我当时的既有观点
  • 每十年只能有一篇入选

这样的选择标准一定是非常苛刻也非常主观的。如果你认为我漏掉了什么,也许你也可以编辑一份你的论文清单。

论排中律在数学上,特别是函数理论中的重要性(1923)

直觉主义的建立早于“计算理论”,但前者对后者的建立至关重要。Luitzen Egbertus Jan Brouwer的早期构想其实是对证明法的一个批判,但是Arend Heyting在后来的工作中把直觉主义结合应用到了数理逻辑中。

我选择Brouwer的论文是因为它抛弃排中律强调价值的建设。Brouwer并不认为一个命题如果不为假,则必为真。他认为,命题必须要被严谨地正面证明为真才对。

作为一名程序员,计算一个值和仅仅表示这个值的存在两者之间之间的区别是非常紧密相关的。更重要的是,起源于Brouwer想法的构造数学在随后的类型论发展中起了至关重要的作用。

论可计算数及其在可判定性问题上的应用(1936)

Alan Turing之所以在编程社区之外被众所周知,是因为他在第二次世界大战中破解了密码系统,和他所遭到的迫害而且最后自杀身亡。这篇论文诞生于战争之前,当时他还是个年轻的博士生。

我发现自己很难用直觉来理解图灵所描述的一个现象——不可计算数。我对于认为计算本身有硬性限制,这种说法既让人费解,又充满魅力。

在著名的判定性问题上,尽管图灵机和Alonzo Church的λ演算都被证明了是不朽的模拟计算方法,Turing的文章还是因为勉强打败了Church提出的解决方案被出版。

通信的数学理论(1948)

我清楚得记得还在念大学的时候读到这篇论文时的震撼。我之前认为信息就跟幽默感和美感一样,是无形的。这篇论文让信息突然变成了准确而可量化的了。

Claude E. Shannon是信息论的鼻祖,他让现代信息和通讯技术成为了可能。

非合作博弈(1950)

这篇并不是跟计算相关的,严格意义上它甚至都不能算作一篇论文。John Nash的博士学位论文整整26页却只有2个引用,其中一个还是引用他自己以前的一篇论文。在这篇文章中,Nash阐述了一个基于非合作博弈的数学理论。这个理论在经济学和冷战策略上有着深远的影响,并且最终带给了Nash诺贝尔经济学奖。

就算你仅仅想看看Nash因为无法用当时的打字机打出来而手写的那些数学符号,这篇论文已经很值得一读了。

递归函数下的符号表达式及计算机器(第一部分)(1960)

给出John McCarthy)这篇Lisp的开山之作不足为奇。这篇文章把编程原理讲解地细致到了原子级别。

Carl Sagan说过要想完完全全从零开始做一个苹果派,你先得创造一个宇宙。McCarthy在这篇文章告诉我们,要想完完全全从零开始做计算,你只需要先创造S表达式。

分布式系统中的时间,时钟和事件顺序(1978)

Leslie Lamport在这篇文章里研究了同步和因果关系的极限,可以说能让人想起爱因斯坦的相对论。虽然他的文章在互联网出现之前就有了(论文参考了ARPA net),但是这篇论文开始谈及到与现代分布式系统密切相关的协调问题。

Lamport在2013年获得了图灵奖。有个笑话是:每个人都知道他早就该得图灵奖了,但大家用了很长时间才达成了“同步”一致。

概率加密(1983)

现代加密方法往往依赖于陷门函数 —— 它们的计算量不大,但几乎无法被逆推。这使得人们可以花费很小的代价加密数据,并且可以很有信心的说这是不可逆转的过程,而且在不知道关键信息的情况下解密数据是不可能的。RSA非对称密码体系)就是一个著名的例子。

但这类方法有个漏洞,即它们仍然允许密码破译者获得加密数据的部分信息。在这篇文章中, Shafi GoldwasserSilvio Micali提出且证明了一种弥补这个漏洞的方法——用随机的方式使加密过程不确定。

编写自成长的语言(1998)

编写代码是非常有意思的,开发一门语言同样如此。在这篇论文中,Guy Steele一开始让单词只有一种意思,然后再让单词同时具有多种意思。他提出了一个很好的观点,成长是一门语言的关键,其能力应该能随着时间的推移而改变,在人们编写代码的时候就能够诞生新的特性。

这个论点最先是在一次演讲中被人们所知道的。

实用的拜占庭容错和实时恢复(2002)

互联网是个很可怕的地方。网络和服务不仅可能完全无法使用,有时也会出现各种奇怪或恶意的行为,甚至互相损害。

做一个可容错的分布式系统常常会被称为“拜占庭将军难题”——意思是假想好几只军队需要协同合作才能成功攻城,但领导他们的将军们却并不完全可靠。

在这篇文章里,Miguel CastroBarbara Liskov描述了一个很有效率的算法,来保证即使三分之一的节点以任何恶意的形式失效,系统仍然是健康的。

对今天的分布式系统而言,这类算法非常有用。比如比特币系统,用了这种算法它只要没失去一半以上的计算能力,都可保证可用。

命题类型(2014)

Philip Wadler的任何一篇论文都可以上榜。这篇论文在我写作的时候仍然是草稿,却可谓是新的经典之作,论文中Walder的引用范围从电影独立日乐团双杰,他揭露了Curry-Howard同构性这种精妙对称性的本质。

同构性记录了逻辑命题和函数式程序种类之间非同寻常的关系。更重要的是,论文的开篇引用了Brouwer在1923年的论文中提出的直觉主义,作为函数对应于传统的直觉主义的构造性证明,这篇论文验证了直觉主义的重要性。

本文在我心中占有特殊的地位,因为在Wadlerd发布最新起草的文章的那个早上,我正好在做关于Curry-Howard同构性的演讲。但幸运的是,其内容没有什么实质性的改变,因而我没有给观众过时的信息。)

总结

我开始写这篇文章的时候正在抱怨我所在行业的短视。尽管我们这个行业的历史不长,从业者仍然对历史很不熟悉。我之前听说,有人问Bjarne Stroustrup,把lambda表达式引入C++是不是因为lambda表达式是个新潮的玩意儿——lambda演算可以追溯到20世纪30年代,比C++要年纪大多了。

但当回顾这份清单上的计算机科学家们的背景时,我不得不为自己的短视感到惊讶。上面说的这12个科学家中,有10个都是男性,且为白人。

因此,我想总结说,除非我有严重的偏见,我们仅仅用到了人类才华总和中很小的一部分。当我思考过去百年我们在计算机科学里走了多远的时候,我无法想象如果能调用更多的聪明才智,下个百年我们会有多么伟大的成就。

from:http://www.techug.com/100-years-of-computer-science

协变(Covariance)与逆变(contravariance)

许多程序设计语言类型系统支持子类型。例如,如果CatAnimal的子类型,那么Cat类型的表达式可用于任何出现Animal类型表达式的地方。所谓的变型(variance)是指如何根据组成类型之间的子类型关系,来确定更复杂的类型之间(例如Cat列表之于Animal列表,回传Cat的函数之于回传Animal的函数…等等)的子类型关系。当我们用类型构造出更复杂的类型,原本类型的子类型性质可能被保持、反转、或忽略───取决于类型构造器英语type constructor的变型性质。例如在C#中:

  • IEnumerable<Cat>IEnumerable<Animal>的子类型,因为类型构造器IEnumerable<T>是协变的(covariant)。注意到复杂类型IEnumerable的子类型关系和其接口中的参数类型是一致的,亦即,参数类型之间的子类型关系被保持住了。
  • Action<Cat>Action<Animal>的超类型,因为类型构造器Action<T>是逆变的(contravariant)。(在此,Action<T>被用来表示一个参数类型为Tsub-T一级函数英语First-class function)。注意到T的子类型关系在复杂类型Action的封装下是反转的,但是当它被视为函数的参数时其子类型关系是被保持的。
  • IList<Cat>IList<Animal>彼此之间没有子类型关系。因为IList<T>类型构造器是不变的(invariant),所以参数类型之间的子类型关系被忽略了。

编程语言的设计者在制定数组、继承、泛型数据类等的类型规则时,必须将“变型”列入考量。将类型构造器设计成是协变、逆变而非不变的,可以让更多的程序俱备良好的类型。另一方面,程序员经常觉得逆变是不直观的;如果为了避免运行时期错误而精确追踪变型,可能导致复杂的类型规则。为了保持类型系统简单同时允许有用的编程,一个编程语言可能把类型构造器视为不变的,即使它被视为可变也是安全的;或是把类型构造器视为协变的,即使这样可能会违反类型安全。

在一门程序设计语言的类型系统中,一个类型规则或者类型构造器是:

  • 协变(covariant),如果它保持了子类型序关系≦。该序关系是:子类型≦基类型。
  • 逆变(contravariant),如果它逆转了子类型序关系。
  • 不变(invariant),如果上述两种均不适用。

C#

Java

Scala

Arrays covariance

+

(unsafe at runtime)

+

(unsafe at runtime)

_

(arrays are invariant by design)

Though, there is support for Java’s “covariant” arrays, of course.

Arrays contravariance

_

_

_

Generics variance

(covariance/contravariance)

+

Defined by a generic type creator (definition-site).

(Restricted to generic interfaces and generic delegates)

+

Defined by clients of generic type using wildcards (use-site).

+

Defined by a generic type creator (definition-site).

Also, there are existential types that cover Java’s wildcards functionality.

Overriding: return type covariance

_

+

+

Overriding: parameter type contravariance

_

_

_

【参见】

Covariance and contravariance http://en.wikipedia.org/wiki/Covariance_and_contravariance_(computer_science)

http://zh.wikipedia.org/wiki/%E9%A1%9E%E5%9E%8B%E7%B3%BB%E7%B5%B1

Comparing covariance/contravariance rules in C#, Java and Scala
http://www.codeproject.com/Articles/899319/Comparing-covariance-contravariance-rules