1 /*
2 * Generate packet error rates for OFDM rates given signal level and
3 * packet length.
4 */
5
6 #include <stdio.h>
7 #include <unistd.h>
8 #include <math.h>
9 #include <stdlib.h>
10 #include <string.h>
11 #include <errno.h>
12
13 #include "wmediumd.h"
14
15 #define ARRAY_SIZE(a) (sizeof(a) / sizeof(a[0]))
16
17 /* Code rates for convolutional codes */
18 enum fec_rate {
19 FEC_RATE_1_2,
20 FEC_RATE_2_3,
21 FEC_RATE_3_4,
22 };
23
24 struct rate {
25 int mbps;
26 int mqam;
27 enum fec_rate fec;
28 };
29
30 /*
31 * rate sets are defined in drivers/net/wireless/mac80211_hwsim.c#hwsim_rates.
32 */
33 static struct rate rateset[] = {
34 /*
35 * XXX:
36 * For rate = 1, 2, 5.5, 11 Mbps, we will use mqam and fec of closest
37 * rate. Because these rates are not OFDM rate.
38 */
39 { .mbps = 10, .mqam = 2, .fec = FEC_RATE_1_2 },
40 { .mbps = 20, .mqam = 2, .fec = FEC_RATE_1_2 },
41 { .mbps = 55, .mqam = 2, .fec = FEC_RATE_1_2 },
42 { .mbps = 110, .mqam = 4, .fec = FEC_RATE_1_2 },
43 { .mbps = 60, .mqam = 2, .fec = FEC_RATE_1_2 },
44 { .mbps = 90, .mqam = 2, .fec = FEC_RATE_3_4 },
45 { .mbps = 120, .mqam = 4, .fec = FEC_RATE_1_2 },
46 { .mbps = 180, .mqam = 4, .fec = FEC_RATE_3_4 },
47 { .mbps = 240, .mqam = 16, .fec = FEC_RATE_1_2 },
48 { .mbps = 360, .mqam = 16, .fec = FEC_RATE_3_4 },
49 { .mbps = 480, .mqam = 64, .fec = FEC_RATE_2_3 },
50 { .mbps = 540, .mqam = 64, .fec = FEC_RATE_3_4 },
51 };
52 static size_t rate_len = ARRAY_SIZE(rateset);
53
n_choose_k(double n,double k)54 static double n_choose_k(double n, double k)
55 {
56 int i;
57 double c = 1;
58
59 if (n < k || !k)
60 return 0;
61
62 if (k > n - k)
63 k = n - k;
64
65 for (i = 1; i <= k; i++)
66 c *= (n - (k - i)) / i;
67
68 return c;
69 }
70
dot(double * v1,double * v2,int len)71 static double dot(double *v1, double *v2, int len)
72 {
73 int i;
74 double val = 0;
75
76 for (i = 0; i < len; i++)
77 val += v1[i] * v2[i];
78
79 return val;
80 }
81
82 /*
83 * Compute bit error rate for BPSK at a given SNR.
84 * See http://en.wikipedia.org/wiki/Phase-shift_keying
85 */
bpsk_ber(double snr_db)86 static double bpsk_ber(double snr_db)
87 {
88 double snr = pow(10, (snr_db / 10.));
89
90 return .5 * erfc(sqrt(snr));
91 }
92
93 /*
94 * Compute bit error rate for M-QAM at a given SNR.
95 * See http://www.dsplog.com/2012/01/01/symbol-error-rate-16qam-64qam-256qam/
96 */
mqam_ber(int m,double snr_db)97 static double mqam_ber(int m, double snr_db)
98 {
99 double k = sqrt(1. / ((2./3) * (m - 1)));
100 double snr = pow(10, (snr_db / 10.));
101 double e = erfc(k * sqrt(snr));
102 double sqrtm = sqrt(m);
103
104 double b = 2 * (1 - 1./sqrtm) * e;
105 double c = (1 - 2./sqrtm + 1./m) * pow(e, 2);
106 double ser = b - c;
107
108 return ser / log2(m);
109 }
110
111 /*
112 * Compute packet (frame) error rate given a length
113 */
per(double ber,enum fec_rate rate,int frame_len)114 static double per(double ber, enum fec_rate rate, int frame_len)
115 {
116 /* free distances for each fec_rate */
117 int d_free[] = { 10, 6, 5 };
118
119 /* initial rate code coefficients */
120 double a_d[3][10] = {
121 /* FEC_RATE_1_2 */
122 { 11, 0, 38, 0, 193, 0, 1331, 0, 7275, 0 },
123 /* FEC_RATE_2_3 */
124 { 1, 16, 48, 158, 642, 2435, 9174, 34701, 131533, 499312 },
125 /* FEC_RATE_3_4 */
126 { 8, 31, 160, 892, 4512, 23297, 120976, 624304, 3229885, 16721329 }
127 };
128
129 double p_d[ARRAY_SIZE(a_d[0])] = {};
130 double rho = ber;
131 double prob_uncorrected;
132 int k;
133 size_t i;
134
135 for (i = 0; i < ARRAY_SIZE(p_d); i++) {
136 double sum_prob = 0;
137 int d = d_free[rate] + i;
138
139 if (d & 1) {
140 for (k = (d + 1)/2; k <= d; k++)
141 sum_prob += n_choose_k(d, k) * pow(rho, k) *
142 pow(1 - rho, d - k);
143 } else {
144 for (k = d/2 + 1; k <= d; k++)
145 sum_prob += n_choose_k(d, k) * pow(rho, k) *
146 pow(1 - rho, d - k);
147
148 sum_prob += .5 * n_choose_k(d, d/2) * pow(rho, d/2) *
149 pow(1 - rho, d/2);
150 }
151
152 p_d[i] = sum_prob;
153 }
154
155 prob_uncorrected = dot(p_d, a_d[rate], ARRAY_SIZE(a_d[rate]));
156 if (prob_uncorrected > 1)
157 prob_uncorrected = 1;
158
159 return 1.0 - pow(1 - prob_uncorrected, 8 * frame_len);
160 }
161
get_error_prob_from_snr(double snr,unsigned int rate_idx,u32 freq,int frame_len)162 double get_error_prob_from_snr(double snr, unsigned int rate_idx, u32 freq,
163 int frame_len)
164 {
165 int m;
166 enum fec_rate fec;
167 double ber;
168
169 if (snr <= 0.0)
170 return 1.0;
171
172 if (freq > 5000)
173 rate_idx += 4;
174
175 if (rate_idx >= rate_len)
176 return 1.0;
177
178 m = rateset[rate_idx].mqam;
179 fec = rateset[rate_idx].fec;
180
181 if (m == 2)
182 ber = bpsk_ber(snr);
183 else
184 ber = mqam_ber(m, snr);
185
186 return per(ber, fec, frame_len);
187 }
188
get_error_prob_from_per_matrix(struct wmediumd * ctx,double snr,unsigned int rate_idx,u32 freq,int frame_len,struct station * src,struct station * dst)189 static double get_error_prob_from_per_matrix(struct wmediumd *ctx, double snr,
190 unsigned int rate_idx, u32 freq,
191 int frame_len, struct station *src,
192 struct station *dst)
193 {
194 int signal_idx;
195
196 signal_idx = snr + NOISE_LEVEL - ctx->per_matrix_signal_min;
197
198 if (signal_idx < 0)
199 return 1.0;
200
201 if (signal_idx >= ctx->per_matrix_row_num)
202 return 0.0;
203
204 if (freq > 5000)
205 rate_idx += 4;
206
207 if (rate_idx >= rate_len)
208 return 1.0;
209
210 return ctx->per_matrix[signal_idx * rate_len + rate_idx];
211 }
212
read_per_file(struct wmediumd * ctx,const char * file_name)213 int read_per_file(struct wmediumd *ctx, const char *file_name)
214 {
215 FILE *fp;
216 char line[256];
217 int signal;
218 size_t i;
219 float *temp;
220
221 fp = fopen(file_name, "r");
222 if (fp == NULL) {
223 w_flogf(ctx, LOG_ERR, stderr,
224 "fopen failed %s\n", strerror(errno));
225 return EXIT_FAILURE;
226 }
227
228 ctx->per_matrix_signal_min = 1000;
229 while (fscanf(fp, "%s", line) != EOF){
230 if (line[0] == '#') {
231 if (fgets(line, sizeof(line), fp) == NULL) {
232 w_flogf(ctx, LOG_ERR, stderr,
233 "Failed to read comment line\n");
234 return EXIT_FAILURE;
235 }
236 continue;
237 }
238
239 signal = atoi(line);
240 if (ctx->per_matrix_signal_min > signal)
241 ctx->per_matrix_signal_min = signal;
242
243 if (signal - ctx->per_matrix_signal_min < 0) {
244 w_flogf(ctx, LOG_ERR, stderr,
245 "%s: invalid signal=%d\n", __func__, signal);
246 return EXIT_FAILURE;
247 }
248
249 temp = realloc(ctx->per_matrix, sizeof(float) * rate_len *
250 ++ctx->per_matrix_row_num);
251 if (temp == NULL) {
252 w_flogf(ctx, LOG_ERR, stderr,
253 "Out of memory(PER file)\n");
254 return EXIT_FAILURE;
255 }
256 ctx->per_matrix = temp;
257
258 for (i = 0; i < rate_len; i++) {
259 if (fscanf(fp, "%f", &ctx->per_matrix[
260 (signal - ctx->per_matrix_signal_min) *
261 rate_len + i]) == EOF) {
262 w_flogf(ctx, LOG_ERR, stderr,
263 "Not enough rate found\n");
264 return EXIT_FAILURE;
265 }
266 }
267 }
268
269 ctx->get_error_prob = get_error_prob_from_per_matrix;
270
271 return EXIT_SUCCESS;
272 }
273
get_max_index(void)274 int get_max_index(void)
275 {
276 return rate_len - 1;
277 }
278
index_to_rate(size_t index,u32 freq)279 int index_to_rate(size_t index, u32 freq)
280 {
281 if (freq > 5000)
282 index += 4;
283
284 if (index >= rate_len)
285 index = rate_len - 1;
286
287 return rateset[index].mbps;
288 }
289