袁泰凌，徐昆

1. 清华大学计算机科学与技术系，北京 100084； 2. 普适计算教育部重点实验室，北京 100084

0 引 言

快速响应矩阵码(quick response code，QR code)简称二维码，是一种正方形符号，广泛应用于商品识别、广告、在线支付和疫情防控等场景。二维码符号的最小单元是模块，即深色或浅色的小正方形。二维码的版本决定了每条边上的模块数量，如图1所示，二维码版本越大，每条边上的模块数量越多。

图1 不同版本的二维码示意图Fig.1 QR code examples with different versions((a) version 1; (b) version 6; (c) version 11)

二维码使用了纠错码，因此其对模块错误有一定纠错能力。减小二维码的版本能够在不减小模块大小的前提下节省面积，或者在不改变面积的前提下增大模块大小以提高模块正确识别的概率。

为了提高二维码的数据容量，现有研究工作主要采用了不兼容标准二维码的编码格式。例如使用彩色模块、修改模块排布、修改位流编码步骤等。这些方案都需要使用专门的扫码器才能读取。考虑到扫码用户一般有通用的标准二维码扫码器，而不一定有专门的扫码器，因此这些二维码的普适性较差。如何在兼容二维码标准的前提下最大化数据容量是一个待解决的问题。

与上述研究工作不同的是，本文在符合二维码标准的前提下最小化位流长度，从而最大化数据容量。本文算法输出的位流与标准算法(国家质量技术监督局，2000)、开源编码器ZXing(https://code. google.com/p/zxing)、商业编码器“草料二维码生成器”(http://cli.im/)相比，长度相同或更短。一方面，信源编码问题转换为动态规划问题，提出了计算最短位流的算法；……