高等
函
授 学报
(
自然 科学 版
)
1 9 96
年第
3
期
群论
在
纠错
码 中的
应
用
黄
万
徽
本 文论 述 了 群论 在 纠 错码 中
的
应 用
,
从 设 有 长度 为
2
的字
,
它 们 共有
2
2
一
4
个
,
由
而 说 明计 算机 科学 具
有
牢
固
的数 学基
础
.
同 它 们构 成 的码
s
:
一 {
00
,
01
,
1
0
,
1 1
}
,
这 种 编
时
,
也
使
我 们看到 群 论 在 计
算
机科 学 中的应 码 不具 有 抗干 扰 能力
。
因为 当
s
:
中 的一 个 字
用
。
如 10
在
传 递过 程 中第
1
个 码元
1
变 成
。
,
因而 整
一
、
问题 的提出
·
个 码 字 变 成 00
,
由
于
00 亦
为
s
:
中的 字
,
故 我
在计 算 机 的数 据 信息传 递 过 程 中
,
由
于
们 并不能 发现 传递 中是 否 出错
。
但 是
,
如果 我
存在 着 各种干 扰
,
可 能使 二 进制 信 号产 生 失 们选 择
5
2
的
一
个 子 集
c
:
一
弋
00
,
1 1
}
作 为编 码
真现 象
:
即 在传 递 过
程
中
o
可能 变 成
1
,
而
1
可 时 就会 发
生
另
一
种 完 全 不 同的 情
况
.
因 为 此
.
能会变 成
。
。
解决 这个
间
题 的方法 有两 种
:
(l
)
时
01
与 10 均 为废 码
,
而 当
11
在 传递 过
程
中 第
提高 设备 的抗干 扰能 力
。
但
是
,
仅 仅从 物理 角 一 个 由
1
变成
。
,
即
整
个 字成 为
01
时
,
由
于 01
是
度去 提高抗 千扰 能 力并不 能完 全消除 错误 的 废码
,
因
此
我 们发 现 传递过
程
中出现 了错 误
。
出现
。
( 2)
采 取 纠错 的 方法
.
这 种 方
法
是 从 编 对 子 00 也有相 同 的情况
。
但 是
,
这 种编 码有
一
码 上 下功 夫
,
使得 二 进 制数 码 在 传递 中
一
旦 个 缺点
,
即它
只
能发现错 误 不能 纠正 错误
.
因
出错
,
在接收 装置 中就 能立 刻 发现 并 将 其 纠 此
,
我 们还需
要
选 择 另一种 能纠错 的编 码
。
现
正
。
在 我 们考虑 长度为
3
的 字
,
它 们
一
共有
2
3
一
8
}
发送端
}
。
}
形成纠 错
码
{
。
}
接
收
码
}
。
!
检查 纠 错
码
}
个
,
在 它 们 所 组 成 的 字 集
s
:
二 {
0
00
,
0
01
,
介
0
1
0
,
0
1 1
,
1 0 0
,
1 0 1
,
1 1 0
,
1 1
1
}
中
,
我 们选 取 编
匡亚」
码
:
C
:
~ {
0
01
,
1
10
}
.
利
用
此 种编
码
,
我 们 不但
图
1
能 发 现 错
误
,
而 且 能 纠
正
错 误
。
因
为 码 字
0
01
从 图
1
中看到
,
当二进 制 信号从 发送 端发 出
现
错 误
后
将变 成
0
00
,
0
1 1
,
1
01
,
而 码 字
1
10
送 时
,
需
要
按 规 定转 换 成 具有 抗 干 扰 能 力 的 出
现
错 误后 将
变
成
1
1 1
,
1
00
,
01
0
。
故如 果
码
字
纠错 码 后才能 发送 出去
。
在接 收端
,
收到 信号
0
01
在 传递过 程
中
任 何一 个 码 元 出现 了错 误
后立 即进 行
纠
错检 查
,
如果 有错 及 时纠正
.
(
例如某
一
个 码元 由
O
变成
l )
,
整个
码
字 就 会
为 什
么
纠错 码具有发 现 错误和 纠
正
错误 变 为
1
01
,
o
n
或
0
00
,
因
此
可 知 其原 正确
码
为
的能力 呢
?
纠错 码是 按 什么原 则编 制呢
?
这
正
0
01
。
对
于
原 来 正确 的
码
字
1
10
也有 类似 的情
是 本文 要解决 的主 要 问题
。
为此
,
我 们先 介绍 况
,
故 对编 码
C
:
我 们不 但能 发现 错 误 还能 纠
一 些基 本概念
。
正
错 误
。
当 然
,
上 述 编 码 还有 一 个 缺 点
,
它
只
二
、
荃本概 念 能 发 现 并 纠
正
单个 错
误
。
当错 误 超 过两 个 码
首 先
,
我 们称
O
,
1
组 成的 串 为字
,
由它 们 元 时
,
它就 既无 力发现对 无法 纠正 了
。
构成 的 集合称 为码
。
码 中的字 称为 码字
。
不在 三
、
纠 错码 的纠 错能 力
码
中的字 称为废 码
。
码
中每个 二进 制信 号
O
或 由
上
可 知
:
不 同 的编
码
具 有 不 同 的 纠错
1
称为码 元
。
能 力
。
编
码
方式 与 纠错 能 力之 间
到
底有 什
么
下 面我 们列举 有关 纠错 码的 例子
。
联 系
?
为此
,
我 们引进
以
下 定义 和定 理
。
评论0