Tăng tốc độ giải thuật mã hóa huffman cho nén ảnh số bằng GPU

Điều khiển – Cơ điện tử - Truyền thông 
 Đào Huy Du, “Tăng tốc độ giải thuật mã hóa Huffman cho nén ảnh số bằng GPU.” 80 
TĂNG TỐC ĐỘ GIẢI THUẬT MÃ HÓA HUFFMAN 
CHO NÉN ẢNH SỐ BẰNG GPU 
Đào Huy Du* 
Tóm tắt: Trong các phương pháp nén đặc biệt là các phương pháp nén không 
tổn hao nếu muốn kết quả nén đạt tỷ lệ nén cao đồng nghĩa với việc thời gian nén sẽ 
cao. Giải thuật mã hóa Huffman là một giải thuật mã hóa không mất mát thông tin 
được áp dụng vào việc nén các đối tượng (văn bản, hình ảnh,) cần độ chính xác 
cao, tuy nhiên giải thuật này cần một khoảng thời gian khá lớn để thực thi các thao 
tác mã hóa. Trong bài báo này, tác giả đưa ra phương pháp cải tiến giải thuật 
Huffman áp dụng trong nén ảnh có độ phân giải cao bằng cách chia ảnh thành các 
khối con để có thể thực hiện mã hóa song song trên các lõi của GPU. Việc thực thi 
giải thuật đề xuất này được thực thi trên GPU của NVIDIA kết hợp với các thư viện 
hỗ trợ xử lý song song của MatLab, đồng thời, đưa ra kết quả để so sánh hiệu suất 
giữa việc mã hóa có sử dụng và không sử dụng GPU. 
Từ khóa: Paralell Computing, GPU, Huffman, Paralell Coding. 
1. ĐẶT VẤN ĐỀ 
Với mục đích cắt giảm chi phí trong việc lưu trữ ảnh và thời gian để truyền ảnh đi xa 
nhưng vẫn đảm bảo chất lượng của ảnh, nén ảnh là một trong những bước quan trọng nhất 
trong quá trình truyền thông và lưu trữ. 
Nén ảnh được áp dụng rất rộng rãi trong thực tế như: truyền các văn bản dưới dạng đồ 
họa, nén ảnh trong y tế, các ảnh dữ liệu chụp từ vệ tinh v.v... Nén ảnh là kỹ thuật được sử 
dụng để làm giảm kích thước của ảnh bằng cách loại bỏ một số thành phần dư thừa trong 
ảnh hay thay thế các thành phần trong ảnh bằng một thành phần khác nhằm làm giảm kích 
thước ảnh. Phương pháp cắt giảm các thông tin dư thừa trong dữ liệu gốc và làm cho dữ 
liệu sau nén nhỏ hơn rất nhiều so với dữ liệu gốc được gọi là phương pháp nén mất mát 
thông tin. Ngược lại, phương pháp nén mà sau khi giải nén thu được chính xác dữ liệu gốc 
gọi là phương pháp nén không mất mát thông tin [1]. 
Một số ảnh cần độ chính xác cao thường phải áp dụng kỹ thuật mã hóa không mất mát 
thông tin để truyền thông hoặc lưu trữ. Ví dụ trong lĩnh vực y tế, đối với kỹ thuật chụp 
CT-Scanner thì mỗi lát cắt của hình ảnh có thế lên đến 150MB hoặc cao hơn, vì vậy, một 
tập dữ liệu đầy đủ cho một chẩn đoán trung bình có thể từ 200MB đến 400MB [2]. Với 
những dữ liệu ảnh như vậy, độ phân giải sẽ rất lớn và cần nhiều dung lượng lưu trữ và đặc 
biệt chi phí cho thời gian nén và giải nén sẽ cao. 
Giải thuật mã hóa Huffman được sử dụng rộng rãi trong các ứng dụng liên quan đến 
truyền thông, các ứng dụng nén dữ liệu ảnh và video [3] [4], giải thuật này đặc biệt phù 
hợp với những tập dữ liệu lớn nhưng có số lượng các đối tượng xuất hiện trong đó là ít. 
Giải thuật mã hóa Huffman gồm có 2 bước chính: Bước thứ nhất, dữ liệu ảnh đầu vào 
được xử lý để tạo ra cây nhị phân và bảng từ mã; Bước thứ 2, mỗi mức xám trong dữ liệu 
đầu vào được so sánh với bảng từ mã để tạo ra luồng bit nhị phân. Trong bước thứ 2, đây 
là giai đoạn chiếm nhiều thời gian nhất trong các giai đoạn nén Huffman do việc phải đi so 
sánh từng phần tử trong tập dữ liệu với bảng từ mã để tạo ra chuỗi dữ liệu mã hóa. 
Cho dù việc mã hóa Huffman song song là một vấn đề khá phức tạp, song đã có nhiều 
công trình tập trung nghiên cứu như: tác giả P. Berman, M. Karpinski và Y. Nekrich [5] đã 
nghiên cứu việc sử dụng n bộ xử lý để tạo ra bảng từ mã song song, nhưng chưa đề cập 
đến vấn đề mã hóa song song. Trong [6], tác giả trình bày phương pháp giải mã song song 
mà có một bị lỗi trong quá trình truyền từ tập dữ liệu mã hóa. Trong [7], tác giả đề cập đến 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san ACMEC, 07 - 2017 81
ảnh hưởng của các kiến trúc phần cứng khác nhau đến việc mã hóa Huffman theo phương 
pháp động. Các kỹ thuật nén JPEG và MPEG cũng áp dụng phương pháp mã hóa Huffman 
để làm tăng tốc độ nén [8] [9] [10] [11]. 
Với sự ra đời và phát triển nhanh chóng của bộ xử lý đồ họa GPU (Graphics Processing 
Unit) cùng với Kiến trúc thiết bị tính toán hợp nhất CUDA (Compute Unified Device 
Architecture ) của NVIDIA với mô hình xử lý SIMD (Single Instruction Multi Data), 
nhiều nhà nghiên cứu cũng đã tập trung giải quyết các bài toán xử lý dữ liệu trên GPU. 
Trong [12], tác giả đã sử dụng GPU để song song hóa giải thuật mã hóa theo độ dài và đã 
đạt được tốc độ xử lý cao bằng cách giới hạn cho độ dài từ mã; Trong [13], tác giả đã thay 
đổi giải thuật Huffman để tạo ra khối dữ liệu nén và giải nén hoàn toàn độc lập với nhau 
và làm tăng tốc độ lên gấp 3 lần so với mã hóa Huffman tuần tự. 
Trong nghiên cứu này, chúng tôi thực hiện việc mã hóa ảnh mầu có độ phân giải cao 
sử dụng giải thuật Huffman bằng cách tạo ra các ma trận mầu sau đó chia các ma trận 
này thành các khối con để đưa vào thực hiện trên từng lõi của GPU. Kết quả kiểm 
nghiệm cho thấy tốc độ mã hóa và giải mã tăng khoảng 5 lần so với thực hiện giải thuật 
Huffman tuần tự. 
Bài báo được trình bày trong 04 mục: Mục 2 trình bày về kiến trúc CPU-GPU và 
phương thức xử lý của GPU[3]; Mục 3: Mã hóa Huffman song song; Mục 4: Kiểm thử 
Phương pháp mã hóa Huffman song song để thực thi trên GPU và kết quả so sánh việc 
thực hiện giải thuật này trên CPU và GPU; Mục 5: Kết luận. 
2. KIẾN TRÚC BỘ XỬ LÝ ĐỒ HỌA - GPU 
CPU được xem như là bộ não của hệ thống máy tính, các hệ thống máy tính hiện nay 
thường được tích hợp hệ thống card đồ họa; hệ thống này không chỉ phục vụ cho các ứng 
dụng về xử lý đồ họa mà đã được phát triển để có thể thực hiện một số chức năng tính 
toán theo mô hình SIMD. Hệ thống Card đồ họa này được gọi là GPU (Graphics 
Processing Unit). Để thực hiện được các thao tác tính toán một cách hiệu quả, GPU cần 
được hỗ trợ kiến trúc tính toán song song do Nvidia phát triển gọi là CUDA (Compute 
Unified Device Architecture - Kiến trúc thiết bị tính toán hợp nhất) [14]. 
Như được chỉ ra trên hình 1, CPU 
thường chỉ được thiết kế với một vài lõi tuy 
nhiên bộ nhớ Cache có kích thước khá lớn 
nên việc truy cập bộ nhớ không bị giới hạn. 
Trong khi đó, GPU bao gồm hàng trăm lõi 
và có thể xử lý đồng thời hàng nghìn luồng 
lệnh, vì vậy GPU có thể hỗ trợ trong việc 
tăng tốc độ thực hiện công việc đồng thời 
tiết kiệm được chi phí đầu tư 
Qui trình tính toán trên GPU được thực 
thi như sau [14]: 
1. Dữ liệu được chuyển từ bộ nhớ chính 
(trên CPU) đến bộ nhớ của GPU. 
2. Chuyển lệnh cần thao tác từ CPU sang 
GPU. 
3. Mỗi lõi (Core) của GPUsẽ thực thi 
lệnh một cách song song trên tập dữ liệu 
riêng biệt. 
 Hình 1. Luồng xử lý dữ liệu 
trên CUDA [15]. 
Điều khiển – Cơ điện tử - Truyền thông 
 Đào Huy Du, “Tăng tốc độ giải thuật mã hóa Huffman cho nén ảnh số bằng GPU.” 82 
4. Xong khi kết thúc công việc, các Core chuyển kết quả từ bộ nhớ trên GPU về bộ nhớ 
chính của CPU. 
Với sự phát triển nhanh chóng của GPU không chỉ trong lĩnh vực đồ họa mà còn thành 
công trong các kỹ thuật tính toán truyền thống hay song song [16]. Trước đây, mọi thao 
tác tính toán được thực hiện trên CPU, tuy nhiên khi hệ thống máy tính được tích hợp 
GPU thì các thao tác tính toán được đưa vào xử lý trên GPU bằng cách di chuyển dữ liệu 
từ CPU sang GPU và công việc được thực thi nhanh hơn nhờ kỹ thuật xử lý song song 
nhiều luồng dữ liệu trên các lõi của GPU. 
3. MÃ HÓA HUFFMAN SONG SONG 
Mã hóa Hufman được giới thiệu năm 1952 bởi D. A. Huffman [17], giải thuật này là 
một giải thuật mã hóa không mất mát thông tin sử dụng trong nén dữ liệu. Tư tưởng của 
giải thuật sẽ thay thế mỗi đối tượng đầu vào bằng mã bit có độ dài thay đổi, trong đó độ 
dài của mã bit được xác định dựa vào tần suất xuất hiện của đối tượng đó khi một đối 
tượng đầu vào có tần suất xuất hiện càng nhiều sẽ được thay thế bởi mã bit càng ngắn. Để 
thực hiện được, giải thuật Huffman cần thực hiện 2 giai đoạn: (1) Xác định tần suất xuất 
hiện các đối tượng và xây dựng cây nhị phân và bảng mã hoá, (2) Mã hóa dữ liệu. 
Khi kích thước ảnh càng lớn, khoảng thời gian để mã hóa càng kéo dài. Do tính chất xử 
lý của GPU là hoạt động theo mô hình SIMD, nên mỗi lõi trong GPU sẽ đảm nhiệm việc 
thực hiện các thao tác mã hóa các phần tử ảnh tương ứng với mỗi luồng dữ liệu đưa vào đó. 
Để thực hiện được việc mã hóa 
các điểm ảnh song song trên GPU, 
ảnh phải được tách ra thành 3 ma 
trận tương ứng với 3 mầu Red, 
Green, Blue. Gọi ba ma trận đó là 
Rc, Gc và Bc với kích thước của 
mỗi ma trận là mxn; 
Tư tưởng chính trong giải thuật 
được thực hiện thành 04 bước: 
Bước thứ nhất: Tách ảnh mầu 
ban đầu thành 03 ma trận ảnh tương 
đương với 3 mầu cơ bản là Red, 
Green và Blue, bước này được thực 
hiện tuần tự trên CPU. 
Bước thứ 2: Sau khi ảnh chính 
được tách ra thành 3 ma trận tương 
ứng với 3 mầu Red, Green và Blue 
mỗi ma trận sẽ được xây dựng một 
cây nhị phân và bảng từ mã tương 
ứng với các mức xám trong từng ma 
trận đó. Các bước từ tách ma trận, 
xây dựng cây nhị phân, tạo bảng từ 
mã cho mỗi ma trận thành phần đều 
được thực hiện song song trên CPU 
và kết quả của bước này sẽ được lưu tại bộ nhớ của mỗi CPU. 
Bước thứ 3: Sau khi hoàn thành việc xây dựng cây nhị phân và bảng từ mã, mỗi ma 
trận thành phần sẽ được tách ra thành các khối (mỗi khối sẽ tương ứng với một hàng của 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san ACMEC, 07 - 2017 83
ma trận) và kích thước của mỗi khối sẽ là (m-1)x1, số lượng các Block chính bằng số hàng 
của ma trận, nếu ma trận có n-1 hàng tương ứng sẽ có n-1 Block. 
Bước thứ 4: CPU sẽ chuyển các Block vào GPU để thực hiện việc mã hóa. Mỗi Block 
sẽ được thực hiện mã hóa đồng thời trên mỗi Thread của GPU. Nếu GPU càng có nhiều 
Thread thì càng có nhiều Block được mã hóa trong cùng một thời điểm, vì vậy tốc độ mã 
hóa của giải thuật này phụ thuộc vào số lượng Thread của GPU. Mỗi phần tử của ma trận 
sẽ được so sánh với bảng từ mã và tạo ra các mã tương ứng. Mỗi một Block sau khi đã mã 
hóa, giải thuật đề xuất sẽ đi ghép giá trị của các phần tử trong các Block này thành 1 file 
nhị phân. Sau khi thực hiện xong việc tạo ra các File nhị phân kết quả đưa trả về cho CPU, 
CPU tiếp tục ghép các File nhị phân thành một File tổ hợp. 
Trong bước thứ 4, mỗi khi tạo ra được một luồng bit nhị phân mã hóa cho các mức xám 
trong 1 Block, theo nguyên tắc bộ xử lý luôn lưu nội dung của File nhị phân có số bit là 
bội của 8, nếu file nhị phân chưa đạt được kích thước bằng bội của 8, bộ xử lý sẽ tự động 
bổ sung số các bit ‘0’ để độ dài File đạt được độ dài theo đúng quy định. Chính nguyên tắc 
này, gây ra sự nhầm lẫn cho bộ giải mã khi nhận được 1 luồng dữ liệu bit không chính xác 
theo đúng nội dung mã hóa. 
Giải pháp để khắc phục trong giải thuật chúng tôi đã gán thêm vào đầu mỗi File nhị 
phân đã mã hóa kích thước thực của luồng bit mã hóa để khi bộ giải mã nhận và đọc đúng 
nội dung của luồng bit mà không bị nhầm lẫn bởi các bit ‘0’ được bổ sung. Giả sử File 
được mã hóa có nội dung:1010010111101100111001111011110110110 
Độ dài của file là 37, bộ xử lý sẽ bổ sung thêm 3 bit ‘0’, và File mã hóa sẽ là cuối cùng 
sẽ là: 1010010111101100111001111011110110110000. 
Để có thể đọc được đúng độ dài file mã hóa và loại trừ lưu được số bit ‘0’ bổ sung, giải 
thuật này chèn 2byte vào đầu mỗi file để lưu độ dài byte mã hóa. File ví dụ trên sẽ thành : 
00000000001001011010010111101100111001111011110110110000. 
Hình 2. Minh họa giải thuật để xuất. 
Điều khiển – Cơ điện tử - Truyền thông 
 Đào Huy Du, “Tăng tốc độ giải thuật mã hóa Huffman cho nén ảnh số bằng GPU.” 84 
Trong giải thuật 1, 2, 3, 4, 5 trình bày các bước thực hiện thao tác mã hóa song song áp 
dụng cho ảnh mầu 
Giải thuật 1. Tách ma trận mầu thành 3 ma trận thành phần là Red, Green và Blue 
(tuần tự trên CPU). 
Đưa ảnh màu Image(RGB )vào xử lý để tách thành 3 ma trận mầu thành phần là 
Red_Matrix, Green_Matrix và Blue_Matrix 
Algorithm1 ImgMatComp(file_name) 
Input: image(RGB) 
Divide image into Red_Matrix (mxn) 
Divide image into Green_Matrix (mxn) 
Divide image into Blue_Matrix (mxn) 
Output:Red_Matrix, Green_Matrix, Blue_Matrix 
Giải thuật 2. Xác định tần suất xuất hiện các các mức xám trên ba ma trận thành phần 
(song song trên CPU). 
Đối với mỗi ma trận mầu thành phần Red_Matrix, Green_Matrix và Blue_Matrix sẽ 
được chuyển vào 1CPU để thực hiện thao tác tính tần suất xuất hiện của các mức xám 
GreyLevel và kết quả được đưa vào 3 bảng Pro_Table tương đương. 
Algorithm2 Greylevel_Prob 
Input:Matrix(Red_Matrix,Green_Matrix,Blue_Matrix) 
Parfor iii=1:3 // each CPU 
Each (matrix())// each matrix that has size of(m x 
n) as: Red_Matrix, Green_Matrix, Blue_Matrix 
{ 
For I: (0-m) do 
For j: (0-n) do 
{ 
For index:(0-255) do 
Compare GreyLevel[i,j]=index 
Add GreyLevel [i,j]->Pro_table 
quanlity= quanlity +1 
 } 
} 
Output: Prob_table_Red[GreyLevel,quanlity], 
 Prob_table_Green[GreyLevel,quanlity], 
 Prob_table_Blue[GreyLevel,quanlity] 
Giải thuật 3. Xây dựng 03 cây nhị phân tương ứng với ba ma trận thành phần (song 
song trên CPU). 
Mỗi bảng tần xuất Pro_Table sẽ đi xây dựng cây nhị phân Huf_Tree tương ứng bằng 
cách sắp xếp giá trị trong bảng theo giá trị tăng dần và các nút của cây nhị phân được gán 
là các trọng số W của mức xám GreyLevel trong bảng Pro_Table. 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san ACMEC, 07 - 2017 85
Algorithm3 BinaryTree 
Parfor iii=1:3 // each CPU 
Sort Pro_table_(Red, Green, Blue) ascending 
i=n 
while i>=1 do 
if(Huf_tree[i]≠null) 
 T=merge(Huf_Tree[i], Wi[1]) 
 Remove Wi[1] from Wi 
 if (weight(Greylevel) ≠ 1/2i-1)or (Wi≠) 
 if(Next_greylevel[i] ≠i-1 ) 
 Next_greylevel[i-1]= 
next_greylevel[i] 
 Next_greylevel[i]=i-1 
 if(weight(greylevel) > 1/2i-1) 
 Wi-1=merger(Wi-1,Greylevel) 
if(Huf_Tree(i)is odd) 
 Huf_Tree(Next_greylevel[i]=last(Wi)) 
i= Next_greylevel[i] 
Giải thuật 4. Chia mỗi ma trận thành phần thành các khối (Block) và mã hóa mỗi 
block trong ma trận thành phần thành các file nhị phân tương ứng (song song trên CPU). 
Chia các ma trận thành phần các khối và các khối con sẽ được mã hóa đồng thời chính 
bằng số lõi NumberGPUCore của GPU, kết quả mã hóa được lưu trong các file nhị phân 
binarry_file. 
Algorithm4 BinaryBlocks 
thread=NumberGpuCore 
Parfor n=(1÷thread) 
for i= (1:lenght(Huff_Tree)) 
 codeword[i]=’’ 
 parfor xx=gpuarray(1:length(index) ) 
 for ind=1:length(symb) 
 if index(xx)==symb(ind) 
 np_data_t{xx}=np(ind); 
 end 
 end 
end 
convert block into binary_file 
add2bytes(binary_file); 
end 
Giải thuật 5. Ghép các File nhị phân thành File tổ hợp hoàn chỉnh. 
Algorithm5 Mergefile(n); 
 for x=1:n(Binary_File) 
 Final_File(Merge Binary_File); 
 end 
Điều khiển – Cơ điện tử - Truyền thông 
 Đào Huy Du, “Tăng tốc độ giải thuật mã hóa Huffman cho nén ảnh số bằng GPU.” 86 
4. KIỂM THỬ 
Trong phần thử nghiệm cho giải thuật nén Huffman song đề xuất, chúng tôi đã cài đặt 
giải thuật này trên cả CPU và GPU hỗ trợ kiến trúc CUDA của Nvidia có cụ thể như sau: 
Cấu hình CPU GPU 
Phần cứng 
Intel(R)Xeon(R)CPUE3-
1225V2@3.3Ghz@3.3Ghz 
4 Core, 7GB Ram 
NVIDIA Quadro 600, 96 Cores, 
GPU Memory Specs: 1 GB DDR3, 
MaxThreadsPerBlock: 1024 
Phần mềm 
Windows 10, 64-bit 
Operating System. Matlab 
R2014a 
Windows 10, 64-bit Operating System 
Matlab R2014c 
Hai ảnh mầu được chụp với độ phân giải cao và được đưa vào mã hóa là VietnamFlag 
và Flowers: 
Hình 3. Flowers. 
Hình 4. VietNamFlag. 
Cơ sở dữ liệu ảnh như sau: 
Bảng 1. Các thông số dữ liệu ảnh. 
Thử nghiệm thứ nhất: thực hiện nén các ảnh trong cơ sở dữ liệu bằng giải thuật 
Huffman tuần tự trên CPU. 
Thử nghiệm thứ hai: thực hiện giải thuật nén Huffman đề xuất trên GPU. Hai ảnh mầu 
được đưa vào để thực hiện mã hóa sẽ được chia thành các Block con và được đưa đến các 
Core của GPU để xử lý. Cụ thể, với ảnh VietNamFlag sẽ được chia thành 3000 Blocks; 
ảnh Flowers chia thành 3920 Blocks. Hai ảnh này sẽ được xử lý trên 1024 Thread của 96 
Core của GPU. 
Kết quả thu được như sau: 
 Bảng 2. So sánh kết quả của giải thuật được cài đặt trên CPU và GPU. 
Tên ảnh VietNamFlag Flowers 
Dung lượng 5,8MB 24,7MB 
Kích thước 3000 x 4496 3920 x 2205 
Số Block 3000 3920 
Thời gian 
mã hóa(s) 
CPU 1,5027 27,337 
GPU 2,170 4,614 
Tên ảnh Dung lượng Kích thước 
VietNamFlag 5,8MB 3000x4496 
Flowers 24,7MB 3920x2205 
Nghiên cứu khoa học công nghệ 
Tạp chí Nghiên cứu KH&CN quân sự, Số Đặc san ACMEC, 07 - 2017 87
Hình 5. Kết quả mô phỏng giải thuật trên CPU và GPU. 
5. KẾT LUẬN 
Trong bài báo, tác giả đã xây dựng giải thuật Huffman song song để cho phép thực 
hiện song song trên bộ xử lý đồ họa GPU. Trong giải thuật này, các ảnh mầu có kích thước 
lớn được phân chia ra thành các Block, số Block chính bằng số hàng của ma trận, và giá trị 
của mỗi phần tử trong Block tương ứng với một mức xám sẽ được mã hóa dựa trên bảng 
từ mã được xây dựng. Kết quả mã hóa cuối cùng thu được sẽ được lưu thành một file nhị 
phân. Do giải thuật được thiết kế cho phép tách và chuyển các Block vào từng Core của 
GPU để có thể thực hiện các thao tác mã hóa một cách đồng thời cho nhiều Block nên đã 
rút ngắn được khoảng thời gian mã hóa ảnh. Dựa trên kết quả thực thi cho thấy, khoảng 
thời gian rút ngắn được từ 4 đến 5 lần so với khi thực hiện giải thuật này trên CPU. Ngoài 
ra, tốc độ mã hóa cũng phụ thuộc vào số Core của GPU, nếu giải thuật được cài đặt trên 
GPU có càng nhiều Core thì tốc độ tính toán sẽ càng nhanh. 
TÀI LIỆU THAM KHẢO 
[1]. M. Rabbani and P. W. Jones, "Digital Image Compression," vol. Spie, 1991. 
[2]. Anders Eklund, Paul Dufort, Daniel Forsberg and and Stephen LaConte, "Medical 
Image Processing on the GP: Past, Present and," Medical Image Processing, vol. 
17, no. 8, pp. 1073-1094, 2013. 
[3]. M. Adler, "Deflate algorithm," [Online]. Available:  
[4]. ISO/IEC JTC 1/SC 29/WG1 – Coding of Still. [Performance]. ISO/IEC JTC 1/SC 
29/WG1 N6922, 2015. 
[5]. P. Berman,M. Karpinsk and Y. Nekrich, "Approximating Huffman Codes in
Parallel," Journal of Discrete Algorithms, Vols. Vol. 5, no. 3, pp. 479-490, 2007. 
[6]. M. B. a. W. Plandowski, "Guaranteed Synchronization of Huffman Codes with 
Known Position of Decoder," Proceedings of Data Compression Conference, pp. 33-
42, 2009. 
[7]. L.Y. Liu, J.F. Wang, R.J. Wang and J.Y. Lee, "Design and hardware architectures 
for dynamic Huffman coding," Proc. Computers and Digital Techniques, pp. 411-
418, 1995. 
[8]. J.S. Patrick, J.L. Sanders, L.S. DeBrunner and and V.E DeBrunner, "JPEG 
Điều khiển – Cơ điện tử - Truyền thông 
 Đào Huy Du, “Tăng tốc độ giải thuật mã hóa Huffman cho nén ảnh số bằng GPU.” 88 
compression/decopmression via parallel processing," Proc. Signals,Systems and 
Computers, pp. 596-600, 1996.. 
[9]. Y. Nishikawa and S. Kawahito and T. Inoue, "A Parallel Image Compression System 
for High-Speed Cameras," Proc. International Workshop on Imaging Systems and 
Techniques, pp. 53-57, 2005.. 
[10]. S.T. Klein and Y. Wiseman, "Parallel huffman decoding with applications to jpeg 
files," The Computer Journal, vol. 46, p. 487–497, 2003. 
[11]. S. Wahl, H.A. Tantawy, Z. Wang and P. Wener and S. Si, "Exploitation of Context 
Classification for Parallel Pixel Coding in Jpeg-LS," Proc. IEEE International 
Conference on Image Processing, pp. 2001-2004, 2011. 
[12]. A. Balevic, "Parallel Variable-Length Encoding on GPGPUs," Proc. Parallel 
Processing Workshops, pp. 26-35, 2010.. 
[13]. R.L. Cloud, M.L. Curry, H.L. Ward and A. Skjellum and P. Bangalore, 
"Accelerating Lossless Data Compression with GPUs," Journal of Undergraduate 
Research, vol. 3, pp. 26-29, 2009. 
[14]. I. Buck and and J. Nickolls , “NVIDIA CUDA software and GPU parallel computing 
architecture”, In Microprocessor Forum, 2007. 
[15]. Cuda, https://en.wikipedia.org/wiki/CUDA, [Online]. 
[16]. J. D. Owens, M. Houston, D. Luebke, S. Green, J. E. Stone and a. J. C. Phillips, 
"GPU Computing," IEEE Proceedings, Vols. Vol. 96, No. 5, p. DOI: 
10.1109/JPROC.2008.917757, May 2008. 
[17]. D. A. Huffman, "A Method for the Construction of Minimum Redundancy Codes," 
Proceedings of the Institute of Radio Engineers, vol. 40, pp. 1098-1101, 1952. 
ABSTRACT 
ACCELERATING HUFFMAN CODING FOR IMAGE COMPRESSION ON GPU 
Dijkstra's algorithm executed parallel on multi-core processor is the best option, 
but the cost of multi-core processors is extremely expensive. GPU launch to be a 
new choice for the field of parallel computing. There are many research methods to 
build algorithm Dijkstra that allows to run on the graphics processor and give 
positive results in terms of time than the execution on multiple processors. In 
parallel the implementation phase of the algorithm on GPUs requires data copy 
operations from the CPU to the GPU to calculate and vice versa when returning 
results. It is the speed limit of the algorithm calculations. In this paper, the author 
would like to present parallelization method Dijkstra algorithm to execute on the 
GPU with the method that does not copy the data to maximize the speed calculation 
algorithm. 
Keywords: Paralell Computing, GPU, Huffman, Paralell Coding. 
Nhận bài ngày 12 tháng 05 năm 2017 
Hoàn thiện ngày 10 tháng 6 năm 2017 
Chấp nhận đăng ngày 20 tháng 7 năm 2017 
Địa chỉ: Khoa Điện Tử - Trường Đại Học Kỹ Thuật Công Nghiệp Thái Nguyên. 
 * Email: daohuydu@tnut.edu.vn