信道H长度L=3，H = (h0,h1,h2),其中h0=,h1=,h2=; 基本信号类型 x =10或-10,一个完整的信号序列为X = （x0,x1,x2,...，x9）;噪声W = （w0,w1,w2,...,w11）是满足高斯分布的（0,1）范围内的随机数；按照Y = H·X + W公式转换得到一个完整的信号序列Y = （y0,y1,y2,...,y11）。信号接收端需要在已知Y,H的情况下通过Viterbi算法得到满足 min (W)即 min(Y - H·X）的X`序列。
将问题转换为的篱笆图，通过动态规划算法，以min(Y - H·X）为图中每一条边的权值计算公式，从显性序列 Y 推导得到隐性序列 X。
1 package cn.edu.karel.algorithm.wirelesschannel;
2
3 import java.util.Random;
4
5 /**
6 *Decoder类
7 *
8 * @author Karel Zuo
9 * @time 2015.5.18
10 * @version 1.0
11 * @description
12 * 该类模拟无线通信过程，接收信息后采用维特比算法或者枚举算法消除噪音并解码。
13 */
14
15 public class Decoder
16 {
17 /** 接收到的信号*/
18 double receive[];
19 /** 去噪解码后的信息 */
20 int[] message;
21 /** 接收信号的通信信道*/
22 double h[];
23 /** 接收信号的基本信号类型*/
24 int signal[];
25 /**信道矩阵*/
26 double H[][];
27
28 /**
29 * @param receive 接收到的信号（Y）
30 * @return message 除噪并解码后得到的信号
31 */
32 public void decodeByViterbi(
double receive[])
33 {
34 int len = receive.length-(h.length-1);
//原信号长度
35 int n = signal.length;
//信号基本类型数
36 int minRoadIndex[][] =
new int[len][n];
//记录每一个阶段的最短路的序号，1表示前一个X为1,-1表示前一个X为-1
37 double minRoadValue[][] =
new double[len][n];
//记录每一个阶段的从原点到该点最短路的权值
38
39 /**计算每一个阶段的最短路权值和选择最短路*/
40 int i,j;
41 for(i=0;i<len;i++
)
42 {
43 /**初始化原顶点层 */
44 if(i==0
)
45 {
46 minRoadIndex[i][0] = 0
;
47 minRoadIndex[i][1] = 0
;
48
49 minRoadValue[i][0] = h[0]*-10
;
50 minRoadValue[i][1] = h[0]*10
;
51 }
52 else
53 {
54 /**计算各个路径的距离和该Xi到原点S的距离*/
55 int q,p;
56 for(q=0;q<n;q++)
//遍历第Xi的所有可能取值
57 {
58 double temp[] =
new double[2
];
59 for(p=0;p<n;p++)
//遍历Xi-1的所有可能取值
60 {
61 temp[p] = getValue(i, q, p, minRoadIndex)+minRoadValue[i-1
][p];
62 }
63
64 if(temp[0] <temp[1
])
65 {
66 minRoadIndex[i][q] = -1
;
67 minRoadValue[i][q] = temp[0
];
68 }
69 else
70 {
71 minRoadIndex[i][q] = 1
;
72 minRoadValue[i][q] = temp[1
];
73 }
74 }
75 }
76 }
77
78 /** 输出解码结果 */
79 message =
new int[len];
80 if(minRoadValue[len-1][0] < minRoadValue[len-1][1
])
81 message[len-1] = -10
;
82 else
83 message[len-1] = 10
;
84 for(j=len-2;j>=0;j--
)
85 {
86 if(message[j+1] == -10
)
87 message[j] = minRoadIndex[j+1][0]*10
;
88 else
89 message[j] = minRoadIndex[j+1][1]*10
;
90 }
91
92 System.out.println(""
);
93 System.out.println(""
);
94 System.out.print("Viterbi算法解码后的信号 ："
);
95 for(j=0;j<len;j++
)
96 System.out.print(message[j] + " , "
);
97 }
98
99 /**
100 * @param receive 接收到的信号（Y）
101 * @return message 除噪并解码后得到的信号
102 */
103 public void decodeByEnum(
double receive[])
104 {
105 int len_y = receive.length;
//接收信号长度
106 int len_x = len_y-(h.length-1);
//原信号长度
107 int num = (
int) Math.pow(signal.length, len_x );
108 int x[][] =
new int[num][len_x ];
109 double value[] =
new double[num];
110
111 /** 枚举所有信号组合形式及其路径长度*/
112 x =
enmuSignal(len_x ,num);
113
114 int p,q,k;
115 for(p=0;p<num;p++
)
116 {
117 double temp = 0
;
118 for(q=0;q<len_y;q++
)
119 {
120 temp = 0
;
121 for(k=0;k<len_x ;k++
)
122 {
123 temp += x[p][k]*
H[q][k];
124 }
125 value[p] += Math.pow((receive[q]-temp), 2
);
126 }
127 }
128
129 /** 搜索到最短路径的组合 */
130 int minRoad = 0
;
131 double minValue =
value[minRoad];
132 int n;
133 for(n=1;n<num;n++
)
134 {
135 if(value[n]<
minValue)
136 {
137 minRoad =
n;
138 minValue =
value[n];
139 }
140 }
141 /**输出，测试 */
142 System.out.println("枚举算法结果： "
);
143 for(n=0;n<len_x;n++
)
144 System.out.print(x[minRoad][n] + " , "
);
145 System.out.println(""
);
146 }
147
148 /**
149 * 接收信号及其他参数
150 * @param en 发送方类对象
151 */
152 public void getSignal(Encoder en)
153 {
154 this.receive =
new double[(Encoder.sendMessage.length)];
155 this.receive =
Encoder.sendMessage;
156 this.h =
new double[Encoder.h.length];
157 this.h =
Encoder.h;
158 this.signal =
new int[Encoder.signal.length];
159 this.signal =
Encoder.signal;
160
161 /**初始化信道矩阵*/
162 int len = receive.length-(h.length-1
);
163 H =
new double[receive.length][len];
//信道矩阵
164 int i,j;
165 for(i=0;i<len;i++
)
166 {
167 for(j=i;j<(i+h.length);j++
)
168 H[j][i] = h[(j-
i)];
169 }
170 }
171
172 /**
173 * 计算Xi到Xi-1的边长
174 * @param index 当前x的下标
175 * @param cur_X 当前xi的取值序号（0,1）
176 * @param per_X 当前xi-1的取值序号（0,1）
177 * @param minRoadIndex 记录Xi到Xi-1的最短路时，Xi-1的取值
178 * @return value 边长
179 */
180 public double getValue(
int index,
int cur_X,
int per_X,
int minRoadIndex[][])
181 {
182 double value = 0
;
183 int x[] =
new int[10];
//x的序列
184
185 if(cur_X == 0
)
186 x[index] = -10
;
187 else
188 x[index] =10
;
189
190 if(per_X == 0
)
191 x[index-1] = -10
;
192 else
193 x[index-1] = 10
;
194
195
196 if(index >= 2
)
197 {
198 int i;
199 for(i=(index-2);i>=0;i--
)
200 {
201 if(x[i+1] == -10
)
202 x[i] = minRoadIndex[i][0]*10
;
203 else
204 x[i] = minRoadIndex[i][1]*10
;
205 }
206 }
207
208 int i;
209 for(i=0;i<10;i++
)
210 value += x[i]*
H[index][i];
211 value = Math.pow((receive[index]-value),2
);
212
213 return value;
214 }
215
216 /**递归实现信号转态的枚举
217 * @param len X序列的长度
218 * @param num X的组合总数
219 * @return x 所有枚举组合
220 * */
221 public int[][] enmuSignal(
int len,
int num)
222 {
223 int m = 0
;
224 int i[] =
new int[len];
225 int x[][] =
new int[num][len];
226 int n =
signal.length;
227
228 for(i[0]=0;i[0]<n;i[0]++
){
229 for(i[1]=0;i[1]<n;i[1]++
){
230 for(i[2]=0;i[2]<n;i[2]++
){
231 for(i[3]=0;i[3]<n;i[3]++
){
232 for(i[4]=0;i[4]<n;i[4]++
){
233 for(i[5]=0;i[5]<n;i[5]++
){
234 for(i[6]=0;i[6]<n;i[6]++
){
235 for(i[7]=0;i[7]<n;i[7]++
){
236 for(i[8]=0;i[8]<n;i[8]++
){
237 for(i[9]=0;i[9]<n;i[9]++
){
238 int j;
239 for(j=0;j<len;j++
)
240 x[m][j]=
signal[(i[j])];
241 m++
;
242 }
243 }
244 }
245 }
246 }
247 }
248 }
249 }
250 }
251 }
252
253 return x;
254 }
255 }
256
257 /**
258 * Encoder类
259 *
260 * @author Karel Zuo
261 * @time 2015.5.18
262 * @version 1.0
263 * @description
264 * 该类模拟无线通信过程，发送信息 X 经过编码得到H·X ，在传输过程中受到干扰变成 H·X + W ，并被接收。
265 */
266
267 public class Encoder
268 {
269 /** 信道总数 */
270 static final int L = 3
;
271 /** 基本信号 */
272 static final int signal[] = {10,-10
};
273 /** H */
274 static final double h[] = {0.8, 0.4, 0.2
};
275 /** 信号长度 */
276 static final int SUM_X = 10
;
277 /** 噪声数量 */
278 static final int SUM_W = 12
;
279 /** 最终发送的信号 */
280 public static double sendMessage[];
281
282 public Encoder()
283 {
284 sendMessage =
new double[SUM_W];
285 sendMessage =
getMessage(creatMessage());
286 }
287
288 /**
289 * @param signal[] 基本信号
290 * @return message[] 随机产生的一段信号
291 */
292 public int[] creatMessage()
293 {
294 int message[] =
new int[SUM_X];
//随机产生并返回的一段信号信息
295 int i;
296 Random r =
new Random();
297
298 for(i=0;i<SUM_X;i++
)
299 {
300 if(r.nextInt(10) < 5
)
301 message[i] = signal[0
];
302 else
303 message[i] = signal[1
];
304 }
305
306 /**输出，测试结果*/
307 System.out.println(" 随机生成的发送序列 X："
);
308 for(i=0;i<SUM_X;i++
)
309 System.out.print(message[i]+" , "
);
310 System.out.println(" "
);
311
312 return message;
313 }
314
315 /**
316 * @param message[] 原始信号
317 * @return receive[] 接收到的信号
318 */
319 public double[] getMessage(
int message[])
320 {
321 double H[][] =
new double[SUM_W][SUM_X];
//信道矩阵
322 double receive[] =
new double[SUM_W];
//接收信号矩阵
323 int i,j;
324 Random r =
new Random();
325
326 /** 初始化 H 矩阵 */
327 for(i=0;i<SUM_X;i++
)
328 for(j=i;j<(i+h.length);j++
)
329 H[j][i] = h[(j-
i)];
330
331 /** 矩阵运算 Y = H·X +W */
332 for(i=0;i<SUM_W;i++
)
333 {
334 for(j=0;j<SUM_X;j++
)
335 receive[i] += H[i][j]*
message[j];
336 receive[i] +=
r.nextGaussian();
337 }
338
339 /** 输出，测试 */
340 System.out.println(""
);
341 System.out.println(""
);
342 System.out.println(" 输出信号 Y ："
);
343 for(i=0;i<SUM_W;i++
)
344 System.out.println(receive[i] + " , "
);
345 System.out.println(""
);
346
347 return receive;
348 }
349 }
350
351 /**
352 * Test类
353 *
354 * @author Karel Zuo
355 * @time 2015.5.18
356 * @version 1.0
357 * @description
358 * 该类模拟无线通信过程。
359 */
360 public class Test {
361
362 public static void main(String[] args) {
363
364 /** 随机生成信号并用Viterbi算法和枚举算法分别还原信号 */
365 Encoder en =
new Encoder();
366 Decoder de =
new Decoder();
367 de.getSignal(en);
368
369 long startEnum = System.currentTimeMillis();
//记录枚举算法开始时间
370 de.decodeByEnum(de.receive);
371 long endEnum = System.currentTimeMillis();
//记录枚举算法结束时间（Viterbi算法开始时间）
372 long startViterbi = System.currentTimeMillis();
//Viterbi算法开始时间
373 de.decodeByViterbi(de.receive);
374 long endViterbi = System.currentTimeMillis();
//记录Viterbi算法结束时间
375
376
377 /**输出程序运行时间 */
378 System.out.println(" "
);
379 System.out.println("枚举算法执行时间： " + (endEnum -
startEnum));
380 System.out.println("Viterbi算法执行时间： " + (endViterbi -
startViterbi));
381 }
382
383 }
转载于:https://www.cnblogs.com/zuoyouchen/p/4526545.html
总结
以上是生活随笔为你收集整理的Viterbi 算法无线通信信号处理Demo的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
