【kAriOJ】离散数学 构造群码 极大似然法解码
A. 编程题1 构造群码
时间限制 1000 ms 内存限制 65536 KB
题目描述
针对给定H,计算群码编码函数eH,并计算给定字的码字。
输入格式
第一行输入两个整数m,n；（m < n ，n < 10）
第二行输入m × (n - m) 个0或1，也就是矩阵H的上半部分，下半部分单位矩阵自行生成；
第三行输入m比特的字；
输出格式
第一行输出该编码函数能检测到的错误位数；
第二行输出给定字的码字；
输入样例
2 5
1 1 0 0 1 1
1 1输出样例
2
11101能检测到的错误位数，就是0~2^m-1生成的编码和0的非零距离的最小值-1。
编码就直接乘上[I|H]，有个地方害我一直wa的，就是int k=0; if(g&(1<<j))k=1; bn[i]^=k&h[m-j][i];我写成了 bn[i]^=g&(1<<j)&h[m-j][i];
/*
TASK:构造群码
LANG:C++
URL:http://code.bupt.edu.cn/problem/contest/491/problem/A/
*/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define N 30
#define ll long long
using namespace std;
int n,m,h[N][N];
int bm[N],bn[N];
//计算n长度的a的权
int weight(int *a){
int ans=0;
for(int i=1;i<=n;i++)
ans+=a[i];
return ans;
}
//计算最多检测的错误
int getk(){
int ans=100;
//g的二进制即生成的Bm
for(ll g=1;g<1<<m;g++){
memset(bn,0,sizeof bn);
for(int i=1;i<=n;i++)
for(int j=m-1;j>=0;j--){
int k=0;
if(g&(1<<j))k=1;
bn[i]^=k&h[m-j][i];
}
int w=weight(bn);
if(w)ans=min(ans,weight(bn));
}
return ans-1;
}
int main() {
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++){
for(int j=m+1;j<=n;j++)
scanf("%d",&h[i][j]);
h[i][i]=1;
}
printf("%d\n",getk());
for(int i=1;i<=m;i++)
scanf("%d",&bm[i]);
//将bm编码成bn
for(int i=1;i<=n;i++){
bn[i]=0;
for(int j=1;j<=m;j++)
bn[i]^=bm[j]&h[j][i];
}
for(int i=1;i<=n;i++)printf("%d",bn[i]);
return 0;
}A. 编程题2 极大似然法解码
时间限制 1000 ms 内存限制 65536 KB
题目描述
给定群码(m,n)的编码函数e的H，采用极大似然法进行解码 (n<=20)
输入格式
第一行输入两个整数m,n；
第二行输入m × (n - m) 个0或1，也就是矩阵H的上半部分，下半部分单位矩阵自行生成；
第三行输入n比特的字；
输出格式
第一行：输出与e相关的极大似然法能纠错的比特数
第二行：采用极大似然法对给定的字解码后的字
输入样例
3 6
1 1 0 1 0 1 0 1 1
001110输出样例
1
011在所有编码和0的距离时，把编出来的码记录起来，然后解码时遍历所有编码，找到距离最近的，就是答案了。
/*
TASK:极大似然法解码
LANG:C++
URL:http://code.bupt.edu.cn/problem/contest/492/problem/A/
*/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define N 50
#define ll long long
using namespace std;
int n,m,h[N][N];
int bm[N];
ll bn[2000][N];
int tmp[N];
//计算n长度的a的权
int weight(ll a[N]){
int ans=0;
for(int i=1;i<=n;i++)
ans+=a[i];
return ans;
}
//计算最多检测的错误,同时计算得到所有的对应编码
int getk(){
int ans=100;
//g的二进制即生成的Bm
for(ll g=1;g<1<<m;g++){
for(int i=1;i<=n;i++)
for(int j=m-1;j>=0;j--){
int k=0;
if(g&(1<<j))k=1;
bn[g][i]^=k&h[m-j][i];
}
int w=weight(bn[g]);
if(w)ans=min(ans,w);
}
return (ans-1)/2;
}
int getn(){
int mi=100,ans=0;
for(ll g=0;g<1<<m;g++){
int dif=0;
for(int i=1;i<=n;i++){
if(bn[g][i]!=tmp[i])dif++;
}
if(mi>dif){
mi=dif;
ans=g;
}
}
return ans;
}
int main() {
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++){
for(int j=m+1;j<=n;j++)
scanf("%d",&h[i][j]);
h[i][i]=1;
}
printf("%d\n",getk());
for(int i=1;i<=n;i++){
char c;
scanf(" %c",&c);
tmp[i]=c-'0';
}
int ans=getn();
for(int i=m-1;i>=0;i--)
printf("%d",(1<<i)&ans?1:0);
return 0;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2016-11-03 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
