CN109163743B - 一种二维绝对位置测量传感器的编码及解码算法 - Google Patents

Abstract

本发明公开了一种二维绝对位置测量传感器的编码及解码算法。该方法包括：基于M序列的性质构造二维编码，通过循环移位相互转换的n阶M序列作为行组成二维编码，该编码具有窗口特性（编码内任一子阵列只出现一次）；相邻行M序列间相对循环移位值构成的序列被称为移位序列，也具有窗户特性；给出了相应的可实现准确解码的算法，将二维解码问题简化成一维解码问题，大大提高了解码效率；解码算法与移位序列相关，具有一定的容错能力。本发明公开的编码及解码算法为二维绝对位置测量传感器的开发提供理论与方法基础。

Description

一种二维绝对位置测量传感器的编码及解码算法

技术领域

本发明涉及传感器编解码算法领域，具体是一种二维绝对位置测量传感器的编码及解码算法。

背景技术

绝对式传感器具有上电即得测量结果、累计误差小、易于拼接等技术优点，在几何量测量中相比增量式测量传感器具有更强的适用性，同时绝对式测量方法由于受到编码加工工艺和读数系统的限制往往难以实现高分辨率、高速的测量。目前绝对式测量传感器主要应用于角度测量的编码器，由于角度具有一周360度的自然基准，角度测量编码器可实现较高的测量精度，如海德汉的ECN425、EQN437等型号产品可实现25bit的测量分辨率；在更多的高分辨率角度和位移传感器产品中，多采用增量码与绝对码混合的编码结构，利用增量码实现传感器的高分辨率。随着微加工技术的进步和电子技术的发展，绝对式传感器分辨率也可以媲美增量式传感器，如瑞士ECLO传感器。

现有的绝对式位移测量传感器主要为一维测量系统，但在影像测量系统、扫描系统、坐标测量机、机床等领域往往需要进行二维测量，目前的常用做法是在X、Y两个方向分别贴装一维位移传感器来实现二维测量。该做法在测量结构上不可避免引入了阿贝误差，同时不利于系统集成设计。因此研发二维绝对式位移传感器对优化二维数控平台系统集成设计、保证测控精度的具有现实工程价值。

绝对式传感器的核心技术是编码与解码方法，目前一维绝对编码方式主要有格雷码、矩阵码和伪随机码。二维绝对编码是一维编码的扩展，主要有：包含所有可能子阵列的Perfect Maps；除全零子阵列外包含其余所有可能子阵列伪随机序列。这些二维编码虽然满足窗口特性，但是它们的构造方式及解码算法比较复杂，执行起来效率不高。因此，设计出更加高效的编码及解码算法是很有必要的。

发明内容

为了克服上述现有技术的不足，本发明提供了一种二维绝对位置测量传感器的编码及解码算法，基于M序列构造具有窗口特性的二维编码，同时给出了高效的解码算法。

为了达到上述目的，本发明所采用的技术方案为：

一种二维绝对位置测量传感器的编码算法，其特征在于：以2ⁿ-1个通过循环移位相互转换的n阶M序列作为行构成二维编码，且该二维编码满足窗口特性，二维编码中任意一个n×n子阵列在整个二维编码中只出现一次，对应平面内的一个位置；

以第一行的M序列作为初始序列，其余行均是初始序列通过循环移位得到，所有相邻M序列间的相对循环移位值构成的一维序列(称作移位序列)满足窗口特性，即任意连续n-1个元素构成的子序列在整个序列中只存在一次，根据M序列的性质，二维编码中任意一个n×n子阵列的行均为n阶M序列的子序列，子阵列中任意相邻两行在M序列中的位置差值等于这两行所在二维编码行间的相对循环移位值。

一种二维绝对位置测量传感器的解码算法，其特征在于：首先根据子阵列的行在M序列中的位置恢复该子阵列对应的循环移位序列的子序列，然后解码该子序列得到纵向位置值，之后根据移位序列及纵向位置值得到子阵列首行所处M序列相对于初始M序列的循环移位值，最后将该移位值与该行在初始M序列中的位置值相加即得到横向位置值。

所述的一种二维绝对位置测量传感器的解码算法，其特征在于：根据二维编码和子阵列的性质，将解码简化为两个一维解码过程，分别解码M序列和移位序列。

本发明编码算法基于M序列的性质构造具有窗口特性的二维编码，编码内任意一个子阵列均只出现一次，对应平面内的一个位置。同时解码算法将二维解码问题简化为了两个一维解码问题，分别为对M序列和移位序列解码。解码算法具有一定的容错能力，当读取到的子阵列存在一定误差时仍能解码得到正确位置值；其容错能力与组成编码的M序列间相对循环移位相关，当相对移位序列满足更加苛刻的条件时，解码算法的容错能力可进一步提升。

二维编码的移位序列可看作是n-1阶2N元M序列中长度为2ⁿ-1的一段。因为一个完整的n-1阶2N元M序列长度远远大于2ⁿ-1，所以当解码时读取到的子阵列存在误差时，得到的循环移位序列的子序列不存在于移位序列中的概率非常大。因此给出的解码算法具有容错能力。当移位序列是m(m<n)阶2N元M序列时，只要得到的子序列中有m个元素正确，就能解码得到准确的位置。m越小意味着子阵列中可允许出错的行数就越多。当m取1即移位序列中所有的元素均不同时，若子阵列中少于四分之一的行出现误差，仍能解码精确位置。因为出错的行少于四分之一时，恢复的子阵列中错误的值必定少于二分之一，其与移位序列中某个长为n的子序列必有一半以上的值对应相同，可得到其唯一位置。

附图说明

图1二进制M序列的LFSR结构图。

图2二维解码流程图。

图3改进后的二维解码流程图。

具体实施方式

下面结合附图和实施例对本发明进一步说明。

S＝s₀s₁...s_N-1是周期为N＝2ⁿ-1的n阶二进制M序列，基于n阶GF(2)域上的本原多项式p(D)产生，满足以下递推公式：

式中p_v∈{0,1}为本原多项式p(D)的系数，s_-1，s_-2，...，s_-n为初始条件。

S可由公式1表示的n个LFSR(线性反馈移位寄存器)产生，如图1所示。它由n个LFSR级联而成，寄存器的状态就是当前寄存器的内容。寄存器工作时，离散时间每增加一个时间单位，寄存器中的内容就向右移一位，同时产生反馈元素移进最左边的寄存器中。寄存器输出端生成周期为N的M序列

M序列S具有以下性质：

1)移位性：S的移位序列s_is_i+1...s_N-1s₀s₁...s_i-1仍为n阶M序列，与S仅相差i个相位，可通过循环移位实现相互转换。

2)循环性：S满足循环

s_i+m＝p_m-1s_i+m-1+p_m-2s_i+m-2+...+p₁s_i+1，i＝0,1,... (3)

3)窗口特性：S中长度为n的序列s_is_i+1...s_i+n-1被称为子序列，任意一个子序列在S中恰好只出现一次。一个n阶M序列共含有2^n-1个子序列，其中除了序列元素全为零的子序列外，所有非零子序列均包含在内。

定义一个运算W，W_k(S)表示M序列S循环移动k位，即

a_i+k＝s_i，0≤i≤N-1 (4)

a_i+k表示W_k(S)的第i个元素。

令T＝t₀t₁...t_N-1，t₀＝0，t_i∈(0，N)是一个长度为N的n阶序列，其中n-1阶的序列T′＝t′₁t′₂…t′_N-1(t′_i＝t_i+1-t_i)满足窗口特性：任意长为n-1的子序列只出现一次。

本发明构造的二维编码是一个N×N的矩阵，可表示为

G＝(g_i，j)，0≤i,j≤N-1 (5)

其中G的每i行等于

即G的第i行由M序列S循环移动t_i位后的序列组成：

则二维编码G中的元素可表示为：

G的子阵列大小为n×n，以

表示，其中

明显可知G_k,l的任一行均为M序列S的子序列，则G_k,l和G之间有如下关系：

d_i+1-d_i＝t_i+k+1-t_i+k＝t′_i+k (9)

d_i表示G_k,l的第i行

在M序列S内的位置。

对于G的任意两个子阵列G_k1,l1和G_k2,l2，它们在二维编码中所处的行要么相同，要么不同。当它们所处的行相同时，k1＝k2则l1≠l2(否则G_k1,l1和G_k2,l2位于同一位置)。对于某一(i，j)值有

再根据式8可知G_k1,l1≠G_k2,l2。当它们所处的行不同时，k1≠k2，由上文可知序列T′＝t′₁t′₂ ′…t′_N-1满足窗口特性，所以至少存在一个i值，使得t′_i+k1≠t′_i+k2成立。由式9，得

其中

分别为G_k1,l1、G_k2,l2的第i行在M序列S内的位置，故

或

中至少有一个成立。因为M序列具有窗口特性，换句话说也就是处于不同位置的子序列定必定是不同的，所以G_k1,l1和G_k2,l2的第i行不同，即

则G_k1,l1≠G_k2,l2。综上所述，可知二维编码内不存在相同的子阵列，即编码具有窗口特性。

将上述二维编码通过一定的方式刻划在平面上，用传感器件读取平面内的编码子阵列，该子阵列在整个二维编码内的位置就为传感器件所处的位置，得到传感器件位置的过程即为二维解码过程。最简单的方式是创建一个查找表，提前将所有子阵列及其位置储存在表中，解码时依次比对表中的子阵列得到对应的位置。这种方式虽然简单，但需要占用大量的存储空间及运行空间。为了更高效、快速的得到准确的位置，本发明提出了一种解码方式，将二维解码问题简化成一维解码问题，采用已知的一维解码算法分别对M序列S和序列T′进行解码。二维解码的具体过程如图2所示，第一步是解码G_k,l中的行

在M序列S中的位置d_i，恢复序列T′的子序列D＝(d₂-d₁,d₃-d₂,…,d_n-d_n-1)，然后解码该子序列得G_k,l的纵向位置值l；第二步是求得

所处M序列

相对于初始M序列S的循环移位值t₁'+t'₂+...+t_l'_+i-1，则横向位置值k＝d_i+t₁'+t'₂+...+t_l'_+i-1。

序列T′＝t′₁t′₂...t′_N-1是由序列T＝t₀t₁...t_N-1，t_i∈(0,N)的相邻元素差构成，t′_i∈(-N,N)。T′本质上是一个长为N-1的n阶2N元M序列。若序列T′包含所有的子序列时，其长度可达(2N)ⁿ-1，远远大于N-1。因此序列T′中大部分的子序列是不存在的。这使得解码具有一定的容错能力。当传感器件读取到的G_k,l中存在错误的码元时，解码时就会得到错误的D，而它不存在于T′中的概率是相当大的。当D不存在与T′中时，就能知道读取的G_k,l存在误差。

当T′为m(m<n)阶2N元M序列时，解码的容错能力有所提升，因为此时只要D中有m个元素正确，就能得到正确的位置。不妨对序列T′取更加特殊的值，使其所有的元素均不同。若G_k,l中出现错误的行少于四分之一，则仍能精确解码得到传感器的位置。因为出错的行少于四分之一时，解码得到的D中错误的值必少于二分之一，和序列T′中的某个长为n的子序列必有一半以上的值对应相同，就能确定其位置。此时解码算法可进一步改进，如图3所示。第一步仍是解码G_k,l中的行

在M序列S中的位置d_i，恢复D＝(d₂-d₁,d₃-d₂,...,d_n-d_n-1)。然后将D与T′的子序列进行比较，若有一半以上的元素相同，则该子序列在T′中的位置即为纵向位置值l。第二步是选取子阵列中正确的某一行

求得其所处M序列

相对于初始M序列S的循环移位值t₁'+t'₂+...+t_l'_+i-1，得到横向位置值k＝d_i+t₁'+t'₂+...+t_l'_+i-1。

Claims (1)

1.一种二维绝对位置测量传感器的编码算法，其特征在于：以2n-1个通过循环移位相互 转换的n阶M序列作为行构成二维编码，且该二维编码满足窗口特性，二维编码中任意一个n ×n子阵列在整个二维编码中只出现一次，对应平面内的一个位置；以第一行的M序列作为初始序列，其余行均是初始序列通过循环移位得到，所有相邻M 序列间的相对循环移位值构成的一维序列满足窗口特性，即任意连续n-1个元素构成的子 序列在整个序列中只存在一次，根据M序列的性质，二维编码中任意一个n×n子阵列的行均 为n阶M序列的子序列，子阵列中任意相邻两行在M序列中的位置差值等于这两行所在二维 编码相邻行间的相对循环移位值；

首先根据子阵列的行在M序 列中的位置恢复该子阵列对应的循环移位序列的子序列，然后解码该子序列得到纵向位置 值，之后根据移位序列及纵向位置值得到子阵列首行所处M序列相对于初始M序列的循环移 位值，最后将该移位值与该行在初始M序列中的位置值相加即得到横向位置值；

根据 二维编码和子阵列的性质，将解码简化为两个一维解码过程，分别解码M序列和移位序列。

Images