信息论与编码课程实验

% a.m
clear all;
clc;
close all;

file_path = 'data.txt';
[symbols, probabilities, selfinformation] = ProbabilityCalculation(file_path);
disp('信源符号：');
disp(symbols);
disp('信源符号概率：');
disp(probabilities);
disp('自信息量：');
disp(selfinformation);

function [symbols, probabilities, selfinformation] = ProbabilityCalculation(filename)
    % 读取文件
    fileID = fopen(filename, 'r');
    content = fscanf(fileID, '%c');
    fclose(fileID);
    % 统计各个符号的出现次数
    uniqueSymbols = unique(content);
    symbolCounts = zeros(1, length(uniqueSymbols));
    for i = 1:length(uniqueSymbols)
        symbolCounts(i) = sum(content == uniqueSymbols(i));
    end
    % 计算符号出现的概率
    totalSymbols = sum(symbolCounts);
    probabilities = symbolCounts / totalSymbols;
    % 计算自信息量
    selfinformation = -log2(probabilities);
    % 按照概率降序排列符号和概率
    [sortedProbabilities, indices] = sort(probabilities, 'descend');
    symbols = uniqueSymbols(indices);
    probabilities = sortedProbabilities;
    % 返回排序后的符号和对应的概率
end

% b.m
[CODE, L_ave, yita, H] = HuffmanEncoding(probabilities);
% 展示输出码字、平均码长和编码效率
disp(['对应概率:',num2str(probabilities)]);
disp(['对应码字:',CODE]);
disp(['平均码长:',num2str(L_ave)]);
disp(['信源熵:',num2str(H)]);
disp(['编码效率:',num2str(yita)]);

% 调用新增函数进行编码并保存
file_path = 'data.txt';
encodedFilePath = 'encoded_data.txt';
decodedFilePath = 'decoded_data.txt';
EncodeAndSave(file_path, symbols, CODE, encodedFilePath);
HuffmanDecoding(encodedFilePath, symbols, CODE, file_path, decodedFilePath);

% 使用Huffman码本对文件内容进行编码并保存
function EncodeAndSave(file_path, symbols, CODE, encodedFilePath)
    % 读取原始文件内容
    fileID = fopen(file_path, 'r');
    originalContent = fscanf(fileID, '%c');
    fclose(fileID);
    % 初始化编码后的内容字符串
    encodedContent = '';
    % 遍历原始内容的每个字符
    for i = 1:numel(originalContent)
        % 查找当前字符在symbols中的位置
        symbolIndex = strfind(symbols, originalContent(i));
        
        % 如果找到，则根据索引从CODE中获取编码并添加到结果字符串
        if ~isempty(symbolIndex)
            encodedContent = strcat(encodedContent, CODE{symbolIndex});
        else
            error(['未在符号集中找到字符：', originalContent(i)]);
        end
    end
    % 保存编码结果到新文件
    fileID = fopen(encodedFilePath, 'w');
    fprintf(fileID, '%s', encodedContent);
    fclose(fileID);
    disp(['编码内容已保存至：', encodedFilePath]);
end


function [CODE, L_ave, yita, H] = HuffmanEncoding(probabilities)
    p = probabilities;
    N = length(p);
    % 将概率排序并获得单步码字排序
    code = strings(N-1,N);   % 初始化单步过程的码字
    reflect = zeros(N-1,N);  % 初始化位置对应向量
    p_SD = p;                % p_SD为每次得到的概率排序数组
    for i=1:N-1              % i表示排序后第几个符号
        M = length(p_SD);
        [p_SD,reflect(i,1:M)] = sort(p_SD,'descend');% 将概率从大到小进行排序
        code(i,M) = '1';                             % 概率最小的是1
        code(i,M-1) = '0';                           % 概率第二小的暂且定义为0
        p_SD(M-1) = p_SD(M-1) + p_SD(M);             % 将最后两个概率相加
        p_SD(M) = [];
    end
    
    % 根据位置对应向量和单步过程的码字计算对应码字
    CODE = strings(1,N); % 初始化对应码字
    for i = 1:N
        column = i;
        for m = 1:N-1
            [~, column] = find(reflect(m,:) == column);
            CODE(1,i) = strcat(CODE(1,i),code(m,column));
            % 将最小的两个概率映射成一个
            if column == N+1-m
                column = column-1;
            end
        end
    end
    CODE = reverse(CODE);
    
    % 计算平均码长
    for i=1:N
        L(i) = size(char(CODE(1,i)),2);
    end
    L_ave = sum(L.*p);
    H = sum(-p.*log2(p));
    yita = H/L_ave; % 计算编码效率
end

function HuffmanDecoding(encodedFilePath, symbols, CODE, originalFilePath, decodedFilePath)
    % 读取编码后的文件内容
    fileID = fopen(encodedFilePath, 'r');
    encodedContent = fscanf(fileID, '%s');
    fclose(fileID);
    
    % 构建逆码本
    inv_CODE = cell(size(CODE));
    for i = 1:numel(CODE)
        inv_CODE{strcmp(CODE, CODE{i})} = symbols(i);
    end
    
    % 解码过程
    decodedContent = '';
    currentCode = '';
    for i = 1:numel(encodedContent)
        currentCode = [currentCode, encodedContent(i)];
        foundSymbol = false;
        for j = 1:numel(CODE)
            if strcmp(currentCode, CODE{j})
                decodedContent = strcat(decodedContent, inv_CODE{j});
                currentCode = ''; % 重置当前码，开始下一个码的匹配
                foundSymbol = true;
                break;
            end
        end
    end
    
    % 保存解码结果到新文件
    fileID = fopen(decodedFilePath, 'w');
    fprintf(fileID, '%s', decodedContent);
    fclose(fileID);
    disp(['解码内容已保存至：', decodedFilePath]);
    
    % 与原始文件进行对比，计算误码率
    originalFileContent = fileread(originalFilePath);
    errors = sum(strcmp(decodedContent, originalFileContent) == 0);
    totalChars = numel(decodedContent);
    errorRate = errors / totalChars;
    disp(['误码率:', num2str(errorRate)]);
end

% c.m
clear all;
clc;
close all;

%% 设置参数
n = 7;
k = 4;
file_path = 'encoded_data.txt';

%% 读取文件内容
fid = fopen(file_path, 'rt'); % 'rt' 表示读取文本文件
dataStr = fscanf(fid, '%c'); % 读取全部字符
fclose(fid);
% 初始化二进制向量
data_bits = zeros(1, length(dataStr));
% 遍历字符串，转换字符到比特
for i = 1:length(dataStr)
    if dataStr(i) == '1' % 字符'1'转换为二进制1
        data_bits(i) = 1;
    elseif dataStr(i) == '0' % 字符'0'转换为二进制0
        data_bits(i) = 0;
    end
end

%% 编码解码
[Encode0, Encode_str] = HammingEncoding(data_bits, n, k);

% 设定错误转移概率的变量范围
berRange = 0:0.01:0.1; % 误码率从0到10%，以0.5%为步长

% 初始化曲线数据
avgBitErrorRate = zeros(1, length(berRange));
blockErrorRate = zeros(1, length(berRange));

% 遍历每个误码率
for w = 1:length(berRange)
    ber = berRange(w);
    [Encode] = simulateBSC(Encode0, ber);
    [Decode, Decode_str] = HammingDecoding(Encode, n, k);    
    % 计算错误位置
    original_bits = data_bits; % 从原始数据转换而来
    decoded_bits = Decode;     % 从decoded_str转换而来，确保长度一致
    errors_positions = [];     % 初始化错误位置列表
    for i = 1:length(original_bits)
        if original_bits(i) ~= decoded_bits(i)
            errors_positions = [errors_positions, i]; % 记录错误位置
        end
    end 
    total_errors = length(errors_positions);
    total_bits = length(original_bits);
    % 计算平均误比特率
    average_bit_error_rate = total_errors / total_bits;
    % 计算平均误比特率
    block_error_rate = 1 - (1 - average_bit_error_rate)^n;
          
    % 记录数据
    avgBitErrorRate(w) = average_bit_error_rate;
    blockErrorRate(w) = block_error_rate;
end

% 绘制曲线图
figure;

% 绘制曲线图
plot(berRange, avgBitErrorRate, 'r-', 'LineWidth', 2, 'Marker', '.', 'MarkerSize', 6);
% plot(berRange, blockErrorRate, 'b-', 'LineWidth', 2, 'Marker', '.', 'MarkerSize', 6);
% 添加标题和轴标签
title('平均误比特率与二进制对称信道错误转移概率的关系');
xlabel('二进制对称信道错误转移概率 (BER)');
ylabel('平均误比特率');

% 设置坐标轴范围和精度
xlim([0 0.1]);
ylim([0 0.1]);

% 可以选择设置网格线
grid on;




%% 生成矩阵和校验矩阵
function [G, H] = hamming_code_matrices(n, k)
    [H, G, ~, ~] = hammgen(n-k);
end

%% 编码
function [encoded_stream, encode_str] = HammingEncoding(data_bits, n, k)
    % 获取生成矩阵
    [G, ~] = hamming_code_matrices(n, k);
    % disp(G);
    % 初始化编码结果的存储
    encoded_stream = [];
    % 处理整个比特流
    while length(data_bits) >= k
        % 对当前k位数据进行编码
        group = data_bits(1:k);
        % 对当前组进行编码
        encoded_group = mod(group * G, 2); 
        % 累积编码结果
        encoded_stream = [encoded_stream, encoded_group]; 
        % 移动到下一个k位数据
        data_bits = data_bits(k+1:end);
    end    
    % 处理剩余不足k位的数据（如果有的话）
    if ~isempty(data_bits)
        % 补齐到k位
        data_bits(end+1:k) = zeros(1, k - length(data_bits));
        group = data_bits;
        encoded_group = mod(group * G, 2);
        encoded_stream = [encoded_stream, encoded_group];
    end    
    % 显示最终编码后的比特流
    encode_str = num2str(encoded_stream);
end

%% 解码（有纠错）
function [decoded_data, decoded_str] = HammingDecoding(encoded_stream, n, k)    
    [~, H] = hamming_code_matrices(n, k);     
    decoded_data = [];    
    while length(encoded_stream)>=n
        encoded_group = encoded_stream(1:n);        
        encoded_stream = encoded_stream(n+1:end);        
        syndrome = mod(encoded_group * H', 2);
        mat1 = eye(n);
        errvec = mat1*H';
        % 如果syndrome非零，则存在错误
        if any(syndrome)            
            for index=1:n
                if(syndrome==errvec(index,:))
                    encoded_group = mod(encoded_group+mat1(index,:),2);
                end
            end
        end             
        decoded_group = encoded_group(n-k+1:end);
        % 累积解码数据，不忽略任何编码组
        decoded_data = [decoded_data, decoded_group];
    end
    decoded_data = [decoded_data, encoded_stream];
    %disp(['总纠错数：',corrected_errors]);
    % 转换为字符串
    decoded_str = num2str(decoded_data);
end

%% 二进制对称信道
function [transmittedStream] = simulateBSC(encodedStream, ber)
    % 模拟二进制对称信道传输编码后的数据流
    % 输入参数:
    %   encodedStream: 编码后的二进制数据流，1xN的二进制数组
    %   ber: 误码率，一个介于0和1之间的标量
    % 输出参数:
    %   transmittedStream: 通过BSC传输后的数据流
    % 获取数据流的长度
    streamLength = length(encodedStream);
    % 生成随机错误分布，1表示发生错误，0表示无错误
    errorVector = rand(streamLength, 1) < ber;
    % 应用错误到数据流
    transmittedStream = encodedStream;
    transmittedStream(errorVector == 1) = xor(encodedStream(errorVector == 1), 1);
    % 返回经过错误注入的传输数据流
end

% d.m
clear all;
clc;
close all;

%% 设置参数
n = 7;
k = 4;
file_path = 'encoded_data.txt';

%% 读取文件内容
fid = fopen(file_path, 'rt'); % 'rt' 表示读取文本文件
dataStr = fscanf(fid, '%c');  % 读取全部字符
fclose(fid);
% 初始化二进制向量
data_bits = zeros(1, length(dataStr));
% 遍历字符串，转换字符到比特
for i = 1:length(dataStr)
    if dataStr(i) == '1' % 字符'1'转换为二进制1
        data_bits(i) = 1;
    elseif dataStr(i) == '0' % 字符'0'转换为二进制0
        data_bits(i) = 0;
    end
end

%% 编码解码
[Encode, Encode_str] = HammingEncoding(data_bits, n, k);
ber = 0.001; % 设定误码率为0.1%
[G, H] = hamming_code_matrices(n, k);
[Encode] = simulateBSC(Encode, ber);
[Decode, Decode_str] = HammingDecoding(Encode, n, k);
decodedFilePath = 'decoded.txt';
fileID = fopen(decodedFilePath, 'w');
fprintf(fileID, '%s', Decode_str);
fclose(fileID);
disp(['解码内容已保存至：', decodedFilePath]);

%% 计算错误位置
original_bits = data_bits; % 从原始数据转换而来
decoded_bits = Decode;     % 从decoded_str转换而来，确保长度一致
errors_positions = [];     % 初始化错误位置列表
for i = 1:length(original_bits)
    if original_bits(i) ~= decoded_bits(i)
        errors_positions = [errors_positions, i]; % 记录错误位置
    end
end
for i = 1:length(errors_positions)
    disp(['第', num2str(i),'个错误位置 ', ': ', num2str(errors_positions(i))]);
end

%% 平均误比特率和误组率
total_errors = length(errors_positions);
total_bits = length(original_bits);
average_bit_error_rate = total_errors / total_bits;
disp(['平均误比特率: ', num2str(average_bit_error_rate)]);
block_error_rate = 1 - (1 - average_bit_error_rate)^n;
disp(['误组率: ', num2str(block_error_rate)]);

%% 生成矩阵和校验矩阵
function [G, H] = hamming_code_matrices(n, k)
    [H, G, ~, ~] = hammgen(n-k);
end

%% 编码
function [encoded_stream, encode_str] = HammingEncoding(data_bits, n, k)
    % 获取生成矩阵
    [G, ~] = hamming_code_matrices(n, k);
    % disp(G);
    % 初始化编码结果的存储
    encoded_stream = [];
    % 处理整个比特流
    while length(data_bits) >= k
        % 对当前k位数据进行编码
        group = data_bits(1:k);
        % 对当前组进行编码
        encoded_group = mod(group * G, 2); 
        % 累积编码结果
        encoded_stream = [encoded_stream, encoded_group]; 
        % 移动到下一个k位数据
        data_bits = data_bits(k+1:end);
    end    
    % 处理剩余不足k位的数据（如果有的话）
    if ~isempty(data_bits)
        % 补齐到k位
        data_bits(end+1:k) = zeros(1, k - length(data_bits));
        group = data_bits;
        encoded_group = mod(group * G, 2);
        encoded_stream = [encoded_stream, encoded_group];
    end    
    % 显示最终编码后的比特流
    encode_str = num2str(encoded_stream);
end

%% 解码（有纠错）
function [decoded_data, decoded_str] = HammingDecoding(encoded_stream, n, k)    
    [~, H] = hamming_code_matrices(n, k);     
    decoded_data = [];    
    while length(encoded_stream)>=n
        encoded_group = encoded_stream(1:n);        
        encoded_stream = encoded_stream(n+1:end);        
        syndrome = mod(encoded_group * H', 2);
        disp(syndrome);
        mat1 = eye(n);
        errvec = mat1*H';
        % 如果syndrome非零，则存在错误
        if any(syndrome)            
            for index=1:n
                if(syndrome==errvec(index,:))
                    encoded_group = mod(encoded_group+mat1(index,:),2);
                end
            end
        end             
        decoded_group = encoded_group(n-k+1:end);
        % 累积解码数据，不忽略任何编码组
        decoded_data = [decoded_data, decoded_group];
    end
    decoded_data = [decoded_data, encoded_stream];
    %disp(['总纠错数：',corrected_errors]);
    % 转换为字符串
    decoded_str = num2str(decoded_data);
end

%% 二进制对称信道
function [transmittedStream] = simulateBSC(encodedStream, ber)
    % 模拟二进制对称信道传输编码后的数据流
    % 输入参数:
    %   encodedStream: 编码后的二进制数据流，1xN的二进制数组
    %   ber: 误码率，一个介于0和1之间的标量
    % 输出参数:
    %   transmittedStream: 通过BSC传输后的数据流
    % 获取数据流的长度
    streamLength = length(encodedStream);
    % 生成随机错误分布，1表示发生错误，0表示无错误
    errorVector = rand(streamLength, 1) < ber;
    % 应用错误到数据流
    transmittedStream = encodedStream;
    transmittedStream(errorVector == 1) = xor(encodedStream(errorVector == 1), 1);
    % 返回经过错误注入的传输数据流
end